Контрольная работа по "Вычислительная математика"

 

Оглавление

 

Задание № 1

 

Определить  корни уравнения F(x) = 0 графически и  уточнить один из них:

• методом половинного деления,
• методом хорд,
• методом касательных,
• методом секущих,
• методом простой итерации

с точностью  ε = 0.001.

Создать функции, реализующие указанные методы, построить  графическую иллюстрацию методов, результаты проверить с помощью  встроенных функций.

Теоретические сведения

Метод бисекции (деления отрезка пополам)

Метод бисекции или метод деления отрезка пополам — простейший численный метод для решения нелинейных уравнений вида F(x)=0. Предполагается только непрерывность функции F(x).

Задача заключается  в нахождении корней нелинейного уравнения

 

                                      (1.1)

 

Для начала итераций необходимо знать интервал [x_L,x_R] значений x, где находится единственный корень. Произведение значений функции на краях этого интервала получится меньше нуля:

 

                                (1.2)

 

То есть функция меняет знак на данном интервале. Выберем точку  внутри интервала

 

Рис. 1.1 Графическое представление метода бисекций (деления отрезка пополам)

 

  .                                   (1.3)

 

Разобьём этот интервал на два [x_L,x_M] и [x_M,x_R]. Теперь найдём новый интервал, в котором функция меняет знак. Пусть и соответственно корень находится внутри интервала [x_L,x_M]. Тогда обозначим x_R=x_M и повторим описанную процедуру до достижения требуемой точности. За количество итераций N первоначальный отрезок делится в 2^N раз. На рисунке 1.1 приведено графическое представление данного метода.

Ниже приведена программная  реализация данного численного метода в пакете MathCAD:

Данная функция имеет следующие входные параметры:

• F – нелинейная функция F(x);
• x0 – начало интервала на котором производится поиск решения уравнения F(x)=0;
• x1 – конец интервала на котором производится поиск решения уравнения F(x)=0;
• e – точность решения

В случае если на данном интервале решения не обнаружено, функция возвращает ∞.

Метод хорд (метод линейной интерполяции)

Приведём метод, основанный на нахождении x_i+1 по двум предыдущим приближениям x_i и x_i-1 с помощью линейной интерполяции, называемый методом хорд.

Идея метода состоит  в том, что по двум точкам и построить прямую (то есть хорду, соединяющую две точки графика ) и взять в качестве следующего приближения абсциссу точки пересечения этой прямой с осью Ox. Иными словами, приближённо заменить на этом шаге функцию её линейной интерполяцией, найденной по двум значениям x: x_i-1 и x_i. (Линейной интерполяцией функции F(x) назовём такую линейную функцию L(x), значения которой совпадают со значениями F(x) в двух фиксированных точках, в данном случае – в точках x_i-1 и x_i.).

В зависимости от того, лежат ли точки x_i-1 и x_i по разные стороны от корня x* или же по одну и ту же сторону, получаем следующие графические представления:

 

Рис.1.2. Построение последовательного приближения по методу хорд: два случая

 

Итак, очередное последовательное приближение будет зависеть от двух предыдущих: . Найдём выражение для функции . Интерполяционную линейную функцию L(x) будем искать как функцию с угловым коэффициентом, равным разностному отношению:

   ,                            (1.4)

построенному для отрезка  между x_i-1 и x_i, график которой проходит через точку M_i:

.                    (1.5)

Решая уравнение L(x) = 0, находим

,        (1.6)

то есть

                (1.7)

Заметим, что величина k_i может рассматриваться как разностное приближение для производной в точке x_i. Тем самым полученная формула (1.7) – это разностный аналог итерационной формулы метода Ньютона.

Вычисление по формуле  вычисления ведутся по формуле (1.7) при i=1,2,3…, начиная с двух приближений x₀ и x₁, взятых, по возможности, поближе к корню x*. При этом не предполагается, что x* лежит между x₀ и x₁ (и что значения функции F в точках x₀ и x₁ имеют разные знаки). При этом не гарантируется, что корень попадёт на отрезок между x_i-1 и x_i на каком-либо следующем шаге (хотя это и не исключено). В таком случае затруднительно дать оценку погрешности, с которой x_i+1 приближает истинное значение корня x*, поэтому довольствуются таким эмпирическим правилом: вычисления прекращают, когда будет выполнено неравенство , где  – желаемая точность нахождения корня. При этом полагают приближённое значение корня равным .

Приведем программную  реализацию метода хорд в пакете MathCAD:

Данная функция имеет следующие входные параметры:

• F – нелинейная функция F(x);
• x₀ – начало интервала на котором производится поиск решения уравнения F(x)=0;
• x₁ – конец интервала на котором производится поиск решения уравнения F(x)=0;
• e – точность решения

В случае если на данном интервале решения не обнаружено, функция возвращает ∞.

Метод касательных (метод Ньютона)

Рассмотрение метода одной касательной позволяет предположить, что итерации станут приближаться к корню ещё быстрее, если мы будем выбирать касательную вместо секущей не только на первом, а на каждом шаге. Ясно, что тогда формула итераций будет иметь вид

                                     (1.8)

Этот метод называется методом касательных, или методом Ньютона. Действительно, последовательные приближения метода Ньютона сходятся гораздо быстрее, чем в общем методе итераций (скорость сходимости приближений в котором, напомним, та же, что у геометрической прогрессии со знаменателем при ).

Рис.1.3. Последовательные приближения метода Ньютона (касательных)

Геометрический смысл  метода Ньютона состоит в том, что на каждом шаге мы строим касательную к графику  точке очередного последовательного приближения x_i, а за следующее приближение x_i+1 берём точку пересечения этой касательной с осью Ox. Тем самым наклон прямой подстраивается на каждом шаге наилучшим образом (ведь кривизну графика, связанную со второй производной, мы не учитываем, и поэтому неизвестно, в какую сторону от касательной отклонится график).

Заметим, что по-другому  идею метода Ньютона мы можем описать  так: на каждом шаге вместо исходного уравнения F(x)=0 мы решаем приближённое, линеаризованное в точке x_i уравнение:

                          (1.9)

в котором левая часть – это многочлен Тейлора первого порядка для функции F(x) в точке x_i, то есть линейная функция

                     (1.10)

Решением линеаризованного уравнения  служит следующее приближение x_i+1, в то время как решением исходного точного уравнения F(x) служит искомый корень x*.

Приведем программную реализацию метода касательных или метода Ньютона в пакете MathCAD:

Данная функция имеет следующие входные параметры:

• F – нелинейная функция F(x);
• x₀ – начальное приближение поиск решения уравнения F(x)=0;
• e – точность решения

Метод секущих

В качестве функции берут любую постоянную , знак которой совпадает со знаком производной в окрестности E (и, в частности, на отрезке, соединяющем x₀ и x*). Постоянная не зависит также и от номера шага i. Тогда формула итераций оказывается очень проста:

и на каждой итерации нужно  один раз вычислить значение функции F(x).

Выясним смысл этой формулы, а также смысл условия о  совпадении знаков и . Рассмотрим прямую, проходящую через точку на графике с угловым коэффициентом . Тогда уравнением этой прямой будет:

.

Найдём точку пересечения  этой прямой с осью из уравнения

,

откуда . Следовательно, эта прямая пересекает ось Ox как раз в точке следующего приближения. Тем самым получаем следующую геометрическую интерпретацию последовательных приближений. Начиная с точки x₀, через соответствующие точки графика проводятся секущие с угловым коэффициентом того же знака, что производная . (Заметим, что, во-первых, значение производной вычислять не обязательно, достаточно лишь знать, убывает функция или возрастает; во-вторых, что прямые, проводимые при разных x_i, имеют один и тот же угловой коэффициент k и, следовательно, параллельны друг другу.) В качестве следующего приближения к корню берётся точка пересечения построенной прямой с осью Ox.

 

Рис. 1.4. Графическая интерпретация метода секущих

На рисунке 1.4 изображены итерации при , в случае . Мы видим, что последовательные точки x_i приближаются к корню, оставаясь всё время с одной стороны от него.

Программная реализация данного метода в пакете MathCAD выглядит так:

Данная функция принимает  следующие параметры:

• F – нелинейная функция F(x);
• x₀ – начало интервала на котором производится поиск решения уравнения F(x)=0;
• ₁ – конец интервала на котором производится поиск решения уравнения F(x)=0;
• e – точность решения

Метод простых итераций

 

Предположим, что уравнение F(x)=0  при помощи некоторых тождественных преобразований приведено к виду F(x)=x.

Заметим, что такое  преобразование можно вести разными способами, и при этом будут получаться разные функции в правой части уравнения. Уравнение F(x)=0  эквивалентно уравнению при любой функции . Таким образом, можно взять и при этом выбрать функцию (или постоянную) так, чтобы функция удовлетворяла тем свойствам, которые понадобятся нам для обеспечения нахождения корня уравнения.

Рис. 1.5. Точка x* – решение уравнения

Для нахождения корня  уравнения  выберем какое-либо начальное приближение x₀ (расположенное, по возможности, близко к корню x*). Далее будем вычислять последующие приближения по формулам

,

то есть, используя каждое вычисленное приближение к корню в качестве аргумента функции в очередном вычислении. Такие вычисления по одной и той же формуле , когда полученное на предыдущем шаге значение используется на последующем шаге, называются итерациями. Итерациями называют часто и сами значения x_i, полученные в этом процессе (то есть, в нашем случае, последовательные приближения к корню).

Заметим тот факт, что x*– корень уравнения , означает, что x* есть абсцисса точки пересечения графика с прямой . Если же при каком-либо x₀ вычислено значение , и взято в качестве нового аргумента функции, то это означает, что через точку графика проводится горизонталь до прямой y=x, а оттуда опускается перпендикуляр на ось Ox. Там и будет находиться новый аргумент x₁.

Ниже приведен программный  код метода простых итераций написанный средствами программирования пакета MathCAD.

 

 

Данная функция имеет  следующие  входные параметры:

• F – нелинейная функция F(x);
• x₀ –начальное приближение при поиске решения уравнения F(x)=0;
• N –число итераций процесса;
• e – точность решения.

Задача 1.1

Площадь кругового сегмента, дуга которого α, определяется формулой:

где α – радиальная мера дуги. Необходимо найти сегмент, площадь которого равна 1/5 площади круга, то есть найти угловую меру дуги сегмента.

Площадь круга определяется по формуле:

,

Из условий получаем равенство:

Таким образом, нам необходимо решить нелинейное уравнение: