Метод простой итерации, называемый также методом последовательного приближения, - это математический алгоритм нахождения значения неизвестной величины путем постепенного ее уточнения. Суть этого метода в том, что, как видно из названия, постепенно выражая из начального приближения последующие, получают все более уточненные результаты. Этот метод используется для поиска значения переменной в заданной функции, а также при решении систем уравнений, как линейных, так и нелинейных.
Рассмотрим, как данный метод реализуется при решении СЛАУ. Метод простой итерации имеет следующий алгоритм:
1. Проверка выполнения условия сходимости в исходной матрице. Теорема о сходимости: если исходная матрица системы имеет диагональное преобладание (т.е, в каждой строке элементы главной диагонали должны быть больше по модулю, чем сумма элементов побочных диагоналей по модулю), то метод простых итераций - сходящийся.
2. Матрица исходной системы не всегда имеет диагональное преобладание. В таких случаях систему можно преобразовать. Уравнения, удовлетворяющие условию сходимости, оставляют нетронутыми, а с неудовлетворяющими составляют линейные комбинации, т.е. умножают, вычитают, складывают уравнения между собой до получения нужного результата.
Если в полученной системе на главной диагонали находятся неудобные коэффициенты, то к обеим частям такого уравнения прибавляют слагаемые вида с i *x i, знаки которых должны совпадать со знаками диагональных элементов.
3. Преобразование полученной системы к нормальному виду:
x - =β - +α*x -
Это можно сделать множеством способов, например, так: из первого уравнения выразить х 1 через другие неизвестные, из второго- х 2 , из третьего- х 3 и т.д. При этом используем формулы:
α ij = -(a ij / a ii)
i = b i /a ii
Следует снова убедиться, что полученная система нормального вида соответствует условию сходимости:
∑ (j=1) |α ij |≤ 1, при этом i= 1,2,...n
4. Начинаем применять, собственно, сам метод последовательных приближений.
x (0) - начальное приближение, выразим через него х (1) , далее через х (1) выразим х (2) . Общая формула а матричном виде выглядит так:
x (n) = β - +α*x (n-1)
Вычисляем, пока не достигнем требуемой точности:
max |x i (k)-x i (k+1) ≤ ε
Итак, давайте разберем на практике метод простой итерации. Пример:
Решить СЛАУ:
4,5x1-1.7x2+3.5x3=2
3.1x1+2.3x2-1.1x3=1
1.8x1+2.5x2+4.7x3=4 с точностью ε=10 -3
Посмотрим, преобладают ли по модулю диагональные элементы.
Мы видим что условию сходимости удовлетворяет лишь третье уравнение. Первое и второе преобразуем, к первому уравнению прибавим второе:
7,6x1+0.6x2+2.4x3=3
Из третьего вычтем первое:
2,7x1+4.2x2+1.2x3=2
Мы преобразовали исходную систему в равноценную:
7,6x1+0.6x2+2.4x3=3
-2,7x1+4.2x2+1.2x3=2
1.8x1+2.5x2+4.7x3=4
Теперь приведем систему к нормальному виду:
x1=0.3947-0.0789x2-0.3158x3
x2=0.4762+0.6429x1-0.2857x3
x3= 0.8511-0.383x1-0.5319x2
Проверяем сходимость итерационного процесса:
0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0.383+ 0.5319= 0.9149 ≤ 1 , т.е. условие выполняется.
0,3947
Начальное приближение х (0) = 0,4762
0,8511
Подставляем данные значения в уравнение нормального вида, получаем следующие значения:
0,08835
x (1) = 0,486793
0,446639
Подставляем новые значения, получаем:
0,215243
x (2) = 0,405396
0,558336
Продолжаем вычисления до того момента, пока не приблизимся к значениям, удовлетворяющим заданному условию.
x (7) = 0,441091
Проверим правильность полученных результатов:
4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3.1*0,1880+2.3*0,441-1.1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977
Результаты, полученные при подстановке найденных значений в исходные уравнения, полностью удовлетворяют условиям уравнения.
Как мы видим, метод простой итерации дает довольно точные результаты, однако для решения этого уравнения нам пришлось потратить много времени и проделать громоздкие вычисления.
ЛАБОРАТОРНАЯ РАБОТА №3-4.
Вариант №5.
Цель работы: научиться решать системы нелинейных уравнений (СНУ) методом простых итераций (МПИ) и методом Ньютона с помощью ЭВМ.
1. Изучить МПИ и метод Ньютона для решения систем нелинейных уравнений.
2. На конкретном примере усвоить порядок решения систем нелинейных уравнений МПИ и методом Ньютона с помощью ЭВМ.
3. Составить программу и с ее помощью решить систему уравнений с точностью .
ПРИМЕР ВЫПОЛНЕНИЯ РАБОТЫ
Задание.
1. Аналитически решить СНУ:
2. Построить рабочие формулы МПИ и метода Ньютона для численного решения системы при начальном приближении: .
3. Составить программу на любом языке программирования, реализующую построенный итерационный процесс.
Решение.
Аналитический метод.
Аналитическим решением СНУ являются точки и .
Метод простых итераций (МПИ).
Для построения рабочих формул МПИ для численного решения системы необходимо вначале привести ее к виду:
Для этого умножим первое уравнение системы на неизвестную постоянную , второе - на , затем сложим их и добавим в обе части уравнения . Получим первое уравнение преобразуемой системы:
Неизвестные постоянные определим из достаточных условий сходимости итерационного процесса:
Запишем эти условия более подробно:
Полагая равными нулю выражения под знаком модуля, получим систему линейных алгебраических уравнений (СЛАУ) 4 порядка с 4 неизвестными :
Для решения системы необходимо вычислить частные производные :
Тогда СЛАУ запишется так:
Заметим, что если частные производные мало изменяются в окрестности начального приближения, то:
Тогда СЛАУ запишется так:
Решением этой системы являются точки , , , . Тогда рабочие формулы МПИ для решения СНУ примут вид:
Для реализации на ЭВМ рабочие формулы можно переписать так:
Итерационный процесс можно начать, задав начальное приближение x 0 =-2, y 0 =-4. Процесс заканчивается при одновременном выполнении двух условий: и . В этом случае значения и являются приближенным значением одного из решений СНУ.
Метод Ньютона.
Для построения рабочих формул метода Ньютона в виде
где , необходимо:
1. Найти матрицу частных производных:
2. Найти определитель этой матрицы:
3. Определить обратную матрицу:
Проведя преобразования:
Получаем рабочую формулу метода Ньютона для реализации на ЭВМ:
Блок-схема МПИ и метода Ньютона для решения СНУ приведена на рисунке 1.
Рис.1 Схемы МПИ и метода Ньютона.
Тексты программ:
Program P3_4; {Iterations}
uses Crt;
var n: integer;
clrscr;
xn:=x-(x-y+2)+(1/2)*(x*y-3);
yn:=y+(2/3)*(x-y+2)+(1/6)*(x*y-3);
writeln (n:3, x:9:5, xn:9:5, (xn-x):9:5, y:9:5, yn:9:5, (yn-y):9:5);
n:=n+1;
until (abs(x-zx)<=eps) and (abs(y-zy)<=eps);
readln;
2) Метод Ньютона:
Program P3_4; {Nyuton}
uses Crt;
var n: integer;
x0,x,xn,y0,y,yn,eps,zx,zy:real;
clrscr;
n:=0; x0:=-2; x:=x0; y0:=-4; y:=y0; eps:=0.001;
writeln (" n x(i) x(i+1) x(i+1)-x(i) y(i) y(i+1) y(i+1)-y(i) ");
xn:=x-(1/(x+y))*(x*x-x*y+2*x+x-y+2);
yn:=y-(1/(x+y))*(x*y*(-y)-3*(-y)+x*y-3);
writeln (n:3, x:9:5, xn:9:5, abs(xn-x):9:5, y:9:5, yn:9:5, abs(yn-y):9:5);
n:=n+1;
until (abs(x-zx)<=eps) and (abs(y-zy)<=eps);
Результаты отработки программы:
· Рис.2 – программы, работающей по методу простых итераций;
· Рис.3 – программы, работающей по методу Ньютона.
Рис.2 Ответ: х(16)≈-3.00023, у(16)≈-1.00001
Рис.3 Ответ: х(8)≈-3.00000, у(8)≈-1.00000
Исследование различных явлений или процессов математическими методами осуществляется с помощью математической модели. Математическая модель представляет собой формализованное описание исследуемого объекта посредством систем линейных, нелинейных или дифференциальных уравнений, систем неравенств, определенного интеграла, многочлена с неизвестными коэффициентами и т. д. Математическая модель должна охватывать важнейшие характеристики исследуемого объекта и отражать связи между ними.
После того, как математическая модель составлена, переходят к постановке вычислительной задачи. При этом устанавливают, какие характеристики математической модели являются исходными (входными)данными, какие - параметрами модели, а какие - выходными данными. Проводится анализ полученной задачи с точки зрения существования и единственности решения.
На следующем этапе выбирается метод решения задачи. Во многих конкретных случаях найти решение задачи в явном виде не представляется возможным, так как оно не выражается через элементарные функции. Такие задачи можно решить лишь приближенно. Под вычислительными (численными) методами подразумеваются приближенные процедуры, позволяющие получать решение в виде конкретных числовых значений. Вычислительные методы, как правило, реализуются на ЭВМ. Для решения одной и той же задачи могут быть использованы различные вычислительные методы, поэтому нужно уметь оценивать качество различных методов и эффективность их применения для данной задачи.
Затем для реализации выбранного вычислительного метода составляется алгоритм и программа для ЭВМ. Современному инженеру важно уметь преобразовать задачу к виду, удобному для реализации на ЭВМ и построить алгоритм решения такой задачи.
В настоящее время широко используются как пакеты, реализующие наиболее общие методы решения широкого круга задач (например, Mathcad ,
MatLAB), так и пакеты, реализующие методы решения специальных задач.
Результаты расчета анализируются и интерпретируются. При необходимости корректируются параметры метода, а иногда математическая модель, и начинается новый цикл решения задачи.
1.1. Постановка задачи
Пусть дана некоторая функция и требуется найти все или некоторые значения , для которых .
Значение , при котором , называется корнем (или решением ) уравнения. Относительно функции часто предполагается, что дважды непрерывно дифференцируема в окрестности корня.
Корень уравнения называется простым, если первая производная функции в точке не равна нулю, т. е. . Если же , то корень называется кратным корнем.
Геометрически корень уравнения есть точка пересечения графика функции с осью абсцисс. На рис. 1 изображен график функции , имеющей четыре корня: два простых и два кратных .
Большинство методов решения уравнения ориентировано на отыскание простых корней.
1.2. Основные этапы отыскания решения
В процессе приближенного отыскания корней уравнения обычно выделяют два этапа: локализация (или отделение) корня и уточнение корня .
Локализация корня заключается в определении отрезка , содержащего один и только один корень. Не существует универсального алгоритма локализации корня. Иногда удобно бывает локализовать корень с помощью построения графика или таблицы значений функции . На наличие корня на отрезке указывает различие знаков функции на концах отрезка. Основанием для этого служит следующая теорема.
Теорема. Если функция непрерывна на отрезке и принимает на его концах значения разных знаков так что , то отрезок содержит по крайней мере один корень уравнения.
Однако корень четной кратности таким образом локализовать нельзя, так как в окрестности такого корня функция имеет постоянный знак. На этапе уточнения корня вычисляют приближенное значение корня с заданной точностью . Приближенное значение корня уточняют с помощью различных итерационных методов. Суть этих методов состоит в последовательном вычислении значений , которые являются приближениями к корню .
1.3. Метод половинного деления
Метод половинного является самым простым и надежным способом решения нелинейного уравнения. Пусть из предварительного анализа известно, что корень уравнения находится на отрезке , т. е. , так, что . Пусть функция непрерывна на отрезке и принимает на концах отрезка значения разных знаков, т.е. .
Разделим отрезок пополам. Получим точку . Вычислим значение функции в этой точке: . Если , то - искомый корень, и задача решена. Если , то - число определённого знака: либо . Тогда либо на концах отрезка , либо на концах отрезка значения функции имеют разные знаки. Обозначим такой отрезок . Очевидно, что и длина отрезка в два раза меньше, чем длина отрезка . Поступим аналогично с отрезком . В результате получим либо корень , либо новый отрезок и т. д. (рис. 2).
Середина -го отрезка . Очевидно, что длина отрезка будет равна , а так как , то
Критерий окончания. Из соотношения (1) следует, что при заданной точности приближения вычисления заканчиваются, когда будет выполнено неравенство или неравенство . Таким образом, количество итераций можно определить заранее. За приближенное значение корня берется величина .
Пример. Найдем приближенно с точностью . Эта задача эквивалентна решению уравнения , или нахождению нуля функции . В качестве начального отрезка возьмем отрезок . На концах этого отрезка функция принимает значения с разными знаками: . Найдем число делений отрезка , необходимых для достижения требуемой точности. Имеем:
Следовательно, не позднее 6-го деления найдем с требуемой точностью, . Результаты вычислений представлены в таблице 1.
Таблица 1
| 1,0000 | 1,0000 | 1,0000 | 1,1250 | 1,1250 | 1,1406 | 1,1406 | |
| 2,0000 | 1,5000 | 1,2500 | 1,2500 | 1,1875 | 1,1875 | 1,1562 | |
| 1,5000 | 1,2500 | 1,1250 | 1,1875 | 1,1406 | 1,1562 | 1,1484 | |
| Зн | - | - | - | - | - | - | - |
| Зн | + | + | + | + | + | + | + |
| 5,5938 | 0,7585 | -0,2959 | 0,1812 | -0,0691 | 0,0532 | -0,0078 | |
| - | 1,0000 | 0,5000 | 0,2500 | 0,1250 | 0,0625 | 0,0312 | 0,0156 |
1.4. Метод простой итерации
Пусть уравнение можно заменить эквивалентным ему уравнением
Выберем каким-либо образом начальное приближение . Вычислим значение функции при и найдем уточненное значение . Подставим теперь в уравнение (1) и получим новое приближение и т. д. Продолжая этот процесс неограниченно, получим последовательность приближений к корню:
Формула (3) является расчетной формулой метода простой итерации.
Если последовательность сходится при , т. е. существует
и функция непрерывна, то, переходя к пределу в (3) и учитывая (4), получим: .
Таким образом, , следовательно, - корень уравнения (2).
Сходимость метода. Сходимость метода простой итерации устанавливает следующая теорема.
Теорема. Пусть функция определена и диффе-ренцируема на отрезке , причем все ее зна-чения . Тогда, если выполняется условие при :
1) процесс итерации сходится независимо от начального значения ;
2) предельное значение является единственным корнем уравнения на отрезке .
Доказательство. Так как и , то можно записать
По теореме о среднем (она утверждает, что если производная функции непрерывна на некотором интервале, то тангенс угла наклона хорды, проведенной между точками и , (т.е. равен производной функции в некоторой промежуточной точке, лежащей между и ) частное в последнем выражении будет равно , где - некоторая промежуточная точка в интервале поиска корня. Следовательно, .
Если ввести обозначение для всего интервала поиска, то предыдущее равенство может быть переписано в виде:
Аналогично . Тогда для будет справедливо неравенство: и т. д. Продолжая эти выкладки дальше, в результате получаем , где - натуральное число. Таким образом, чтобы метод сходился, необходимо выполнение неравенства: .
Отсюда следует, что должно быть меньше единицы. В свою очередь, для всех остальных значений меньших , можно записать: . Число определим из соотношения . Тогда справедливо неравенство (вывод см. ниже): . Если поставить условие, что истинное значение корня должно отличаться от приближенного значения на величину , т.е. , то приближения надо вычислять до тех пор, пока не будет выполнено неравенство
или и тогда .
Вывод неравенства.Рассмотрим два последовательных приближения: и . Отсюда .
Используя теорему о среднем, получим:
тогда на основании условия можно записать:
С другой стороны, пусть . Очевидно, что . Отсюда, учитывая, что , получим
Тогда или .
Используя предыдущую формулу, можно получить:
Перейдём к пределу в равенстве (3), в силу непрерывности функции получим , то есть - корень уравнения (2). Других корней на нет, так как если , то , тогда , где . Равенство нулю будет достигнуто, если . То есть - корень единственный.
Теорема доказана.
Приведение уравнения к виду
для обеспечения выполнения неравенства
В общем случае получить подходящую итерационную форму возможно, проведя равносильное преобразование исходного уравнения, например, умножив его на коэффициент : . Прибавив затем к обеим частям уравнения и обозначив можно потребовать выполнения достаточного условия . Отсюда определяется необходимое значение . Так как условие должно выполняться на всем отрезке , то для выбора следует использовать наибольшее значение на этом отрезке, т.е.
Это соотношение определяет диапазон значений коэффициента , изменяющий величину в пределах .
Обычно принимают .
На рис. 3-6 показаны четыре случая взаимного расположения линий и и соответствующие итерационные процессы. Рис. 3 и 4 соответствуют случаю , и итерационный процесс сходится. При этом, если (рис. 3), сходимость носит односторонний характер, а если (рис. 4), сходимость носит двусторонний, колебательный характер. Рис. 5 и 6 соответствуют случаю - итерационный процесс расходится. При этом может быть односторонняя (рис. 5) и двусторонняя (рис. 6) расходимость.
Погрешность метода. Оценка погрешности была доказана (5).
Критерий окончания. Из оценки (5) следует, что вычисления надо продолжать до выполнения неравенство . Если же , то оценка упрощается: .
Пример 1. Используем метод простой итерации для решения уравнения с точностью . Преобразуем уравнение к виду:
, т. е. .
Нетрудно убедиться, что корень уравнения находится на отрезке . Вычислив значения на концах отрезка, получим: , а , т. е. функция на концах отрезка имеет разные знаки,
поэтому внутри отрезка есть корень. Расположение корня наглядно иллюстрирует рис. 7.
Подсчитаем первую и вторую производные функции :
Так как на отрезке , то производная монотонно возрастает на этом отрезке и принимает максимальное значение на правом конце отрезка, т. е. в точке . Поэтому справедлива оценка:
Таким образом, условие выполнено, и можно воспользоваться критерием окончания вычислений. В табл. 2 приведены приближения, полученные по расчетной формуле. В качестве начального приближения выбрано значение .
Таблица 2
| 0,8415 | 0,8861 | 0,8712 | 0,8774 | 0,8765 |
Критерий окончания выполняется при , . Сходимость двусторонняя, качественный характер такой сходимости представлен на рис. 4. Приближенное значение корня с требуемой точностью .
Пример 2. Решить методом простой итерации уравнение на отрезке с точностью 0,025. Для решения исходное уравнение приводится к виду . Для выбора величины используем приведенную выше формулу . Тогда расчетная формула имеет вид . В качестве начального приближения можно выбрать верхнюю границу заданного отрезка .
| 0,8 | 0,78 |
Так как , то .
1.5. Метод Ньютона (метод касательных)
Метод Ньютона является наиболее эффективным методом решения нелинейных уравнений. Пусть корень , т. е. . Предполагаем, что функция непрерывна на отрезке и дважды непрерывно дифференцируема на интервале . Положим . Проведем касательную к графику функции в точке (рис. 8).
Уравнение касательной будет иметь вид: .
Первое пересечение получим, взяв абсциссу точки пересечения этой касательной с осью , т. е. положив : .
Аналогично поступим с точкой , затем с точкой и т. д., в результате получим последовательность приближений , причем
Формула (6) является расчетной формулой метода Ньютона .
Метод Ньютона можно рассматривать как частный случай метода простых итераций, для которого .
Сходимость метода . Сходимость метода Ньютона устанавливает следующая теорема.
Теорема. Пусть - простой корень уравнения и в некоторой окрестности этого корня функция дважды непрерывно дифференцируема. Тогда найдется такая малая - окрестность корня , что при произвольном выборе начального приближения из этой окрестности итерационная последовательность, определенная по формуле (6) не выходит за пределы этой окрестности и справедлива оценка:
Сходимость метода Ньютона зависит от того, насколько близко к корню выбрано начальное приближение.
Выбор начального приближения. Пусть - отрезок, содержащий корень. Если в качестве начального приближения выбрать тот из концов отрезка, для которого , то итерации (6) сходятся, причем монотонно. Рис. 8 соответствует случаю, когда в качестве начального приближения был выбран правый конец отрезка: (Здесь ).
Погрешность метода. Оценка (7) неудобна для практического использования. На практике пользуются следующие оценки погрешности:
Критерий окончания. Оценка (8) позволяет сформулировать следующий критерий окончания итераций метода Ньютона. При заданной точности вычисления нужно вести до тех пор, пока не будет выполнено неравенство
Пример . Вычислить методом Ньютона отрицательный корень уравнения с точностью до 0,0001. Проведя отделение корня, можно убедиться, что корень локализован на интервале . В этом интервале и . Так как и , то за начальное приближение можно принять .
| -11 | -5183 | 0,6662 | |
| -10,3336 | 307,3 | 4276,8 | 0,0718 |
| -10,2618 | 3,496 | 4185,9 | 0,0008 |
| -10,261 | 0,1477 | - | - |
. Поэтому . Итак, в результате получаем следующее, и на , поэтому .
Так как , то
Назначение сервиса . Онлайн-калькулятор предназначен для отыскания корней уравнения методом итераций .Решение оформляется в формате Word .
Одним из наиболее эффективных способов численного решения уравнений является метод итерации
. Сущность этого метода заключается в следующем. Пусть дано уравнение f(x)=0 .
Заменим его равносильным уравнением
Выберем начальное приближение корня x 0 и подставим его в правую часть уравнения (1). Тогда получим некоторое число
x 1 =φ(x 0). (2)
x n =φ(x n-1) (n=1,2..). (3)
Или ξ=φ(ξ).
Таким образом, предел ξ является корнем уравнения (1) и может быть вычислен по формуле (3) с любой степенью точности.
Рис. 1а Рис. 1б
Рис. 2.
|φ′(x)|>1 - расходящийся процесс
На рис.1а, 1б в окрестности корня |φ′(x)|<1 и процесс итерации сходится. Однако, если рассмотреть случай |φ′(x)|>1, то процесс итерации может быть расходящимся (см. рис.2).
φ′(x n)(x n -x n-1)
Где x n ∈
Тогда получим
|x n+1 -x n |≤φ′(x n)|x n -x n-1 |≤q|x n -x n-1 |
|x 2 -x 1 |≤q|x 1 -x 0 |
|x 3 -x 2 |≤q|x 2 -x 1 |≤q²|x 1 -x 0 |
|x n+1 -x n ≤q n |x 1 -x 0 | (4)
, и следовательно,
(в силу непрерывности функции φ(x))
ξ-x n = φ′(c 1)(ξ-x n-1)+φ′(c)(x n -x n-1)
или
|ξ-x n |≤q|ξ-x n |+q|x n -x n-1 |
, (5)
. (6)
|x n -x n -1 |<ε
Сходимость метода итерации
линейная с коэффициентом сходимости α=q. Действительно, имеем
ξ-x n =φ(ξ)-φ n-1 = φ′(c)·(ξ-x n-1), отсюда |ξ-x n |≤q·|ξ-x n-1 |.
Замечание.
Пусть в некоторой окрестности корня ξ∈(a,b) уравнения x= φ(x) производная φ’(x) сохраняет постоянный знак и выполнено неравенство |φ’(x)|≤q<1. Тогда, если φ’(x) положительна, то последовательные приближения x n = φ(x n -1) сходятся к корню монотонно.
Если же φ’(x) отрицательна, то последовательные приближения колеблются около корня.
Рассмотрим способ представления уравнения f(x)=0 в форме x= φ(x).
Функцию φ(x) необходимо задать такую, чтобы |φ’(x)| была малой величиной в окрестности корня.
Пусть известно m 1 и M 1 - наименьшее и наибольшее значения производной f’(x)
0
x = x - λf(x).
Положим φ(x) = x- λf(x). Подберем параметр λ таким образом, чтобы в окрестности корня ξ выполнялось неравенство
0≤|φ′(x)|=|1-λ·f′(x)|≤q≤1
0≤|1-λM 1 |≤|1-λm 1 |≤q
x n = x n -1 – f(x n)/f’(x).
Процесс нахождения нулей функции методом итераций состоит из следующих этапов:
Пример
. Найти корень уравнения e -x -x=0, x=∈, ε=0.001 (8)
Решение
.
Представим уравнение (8) в форме x=x-λ(e -x -x)
Найдем максимальное значение производной от функции f(x)= e - x -x.
max f′(x)=max(-(e -x +1)) ≈ -1.37. Значение 
. Таким образом, решаем следующее уравнение
x=x+0,73(e - x -x)
Значения последовательных приближений даны в таблице.
| n | x i | f(x i) |
| 1 | 0.0 | 1.0 |
| 2 | 0.73 | -0.2481 |
| 3 | 0.5489 | 0.0287 |
| 4 | 0.5698 | -0.0042 |
| 5 | 0.5668 | 0.0006 |
Расчетная формула метода Ньютона имеет вид:
где n=0,1,2,..
Геометрически метод Ньютона означает, что следующее приближение к корню есть точка пересечения с осью ОХ. касательной, проведенной к графику функцииy=f(x) в точке .
Теорема о сходимости метода Ньютона.
Пусть - простой корень уравнения, в некоторой окрестности которого функция дважды непрерывно дифференцируема.
Тогда найдется такая малая - окрестность корня, что при произвольном выборе начального приближенияиз этой окрестности итерационная последовательность метода Ньютона не выходит за пределы окрестности и справедлива оценка
Метода Ньютона (1) чувствителен к выбору начального приближения x 0 .
На практике для монотонной сходимости метода необходимо :
1-ая производная f(x)
2-ая производная f(x) должна быть знакопостоянна на интервале локализации [ a , b ] изолированного корня;
за начальное приближение x 0 выбирается та граница интервала локализации, на которой произведение функции на ее 2-ю производную больше нуля (f(c)f ’’ (c) > 0 , где с – одна из границ интервала) .
. При заданной точности >
Как указано в теореме, метод Ньютона обладает локальной сходимостью, то есть областью его сходимости является малая окрестность корня .
Неудачный выбор может дать расходящуюся итерационную последовательность.
Метод простой итерации (метод последовательных повторений).
Для применения метода простой итерации следует исходное уравнение преобразовать к виду, удобному для итерации .
Это преобразование можно выполнить различными способами.
Функция называется итерационной функцией.
Расчетная формула метода простой итерации имеет вид:
где n=0,1,2,..
Теорема о сходимости метода простой итерации.
Пусть в некоторой - окрестности корняфункциянепрерывно дифференцируема и удовлетворяет неравенству
где 0 < q < 1 - постоянная.
Тогда независимо от выбора начального приближения из указанной - окрестности итерационная последовательность не выходит из этой окрестности, метод сходится
со скоростью геометрической последовательности и справедлива оценка погрешности:
Критерий окончания итерационного процесса .
При заданной точности >0 вычисления следует вести до тех пор пока не окажется выполненным неравенство
Если величина , то можно использовать более простой критерий окончания итераций:
Если в неравенстве (5) q > 1 , то итерационный метод (4) расходится.
Если в неравенстве (5) q = 1 , то итерационный метод (4) может как сходится так и расходится.
В том случае, если q > = 1 , то итерационный метод (4) расходится и
применяется метод простой итерации с итерационным параметром .
Ключевой момент в применении состоит в эквивалентном преобразовании уравнения :
αf(x) = 0
x = x +αf(x) , (9)
где α – итерационный параметр (вещественная константа).
Расчетная формула метода простой итерации с итерационным параметром имеет вид:
x (n+1) = x (n) + αf(x (n) ) , (10)
где n=0,1,2,..
Итерационный процесс, построенный по форме (10) сходится , если:
1-ая производная функции f(x) знакопостоянна и ограничена на интервале локализации изолированного корня ;
знак итерационного параметра α противоположен знаку 1-ой производной функции f(x) на интервале локализации изолированного корня ;
модуль значения итерационного параметра α оценивается из неравенства
| α | < 2/M , (11)
где М – максимум модуля 1-ой производной функции f(x)
Тогда при таком выборе итерационного параметра метод (10) сходится при любом значении начального приближения, принадлежащем интервалу , со скоростью геометрической прогрессии со знаменателем q равным
где m – минимум модуля 1-ой производной функции f(x) на интервале локализации изолированного корня .
