Расчет систем нелинейных уравнений итерационным методом производится. Методы решения систем нелинейных уравнений
Метод простой итерации, называемый также методом последовательного приближения, - это математический алгоритм нахождения значения неизвестной величины путем постепенного ее уточнения. Суть этого метода в том, что, как видно из названия, постепенно выражая из начального приближения последующие, получают все более уточненные результаты. Этот метод используется для поиска значения переменной в заданной функции, а также при решении систем уравнений, как линейных, так и нелинейных.
Рассмотрим, как данный метод реализуется при решении СЛАУ. Метод простой итерации имеет следующий алгоритм:
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 | - | - |
. Поэтому . Итак, в результате получаем следующее, и на , поэтому .
Так как , то
Решение нелинейных уравнений
Пусть требуется решить уравнение
Где
– нелинейная непрерывная функция.
Методы решения уравнений делятся на прямые и итерационные. Прямые методы – это методы, позволяющие вычислить решение по формуле (например, нахождение корней квадратного уравнения). Итерационные методы – это методы, в которых задается некоторое начальное приближение и строится сходящаяся последовательность приближений к точному решению, причем каждое последующее приближение вычисляется с использованием предыдущих
Полное решение поставленной задачи можно разделить на 3 этапа:
Установить количество, характер и расположение корней уравнения (1).
Найти приближенные значения корней, т.е. указать промежутки, в которых наудится корни (отделить корни).
Найти значение корней с требуемой точностью (уточнить корни).
Существуют различные графические и аналитические методы решения первых двух задач.
Наиболее
наглядный метод отделения корней
уравнения (1) состоит в определении
координат точек пересечения графика
функции
с осью абсцисс. Абсциссы
точек
пересечения графика
с осью
являются
корнями уравнения (1)
Промежутки изоляции корней уравнения (1) можно получить аналитически, опираясь на теоремы о свойствах функций, непрерывных на отрезке.
Если,
например, функция
непрерывна
на отрезке
и
,
то согласно теореме Больцано – Коши,
на отрезке
существует
хотя бы один корень уравнения (1)(нечетное
количество корней).
Если
функция
удовлетворяет
условиям теоремы Больцано-Коши и
монотонна на этом отрезке, то на
существует
только один корень уравнения (1).Таким
образом, уравнение (1) имеет на
единственный
корень, если выполняются условия:
Если функция на заданном интервале непрерывно дифференцируема, то можно воспользоваться следствием из теоремы Ролля, по которому между парой корней всегда находится по крайней мере одна стационарная точка. Алгоритм решения задачи в данном случае будет следующий:
Полезным средством для отделения корней является также использование теоремы Штурма.
Решение третьей задачи осуществляется различными итерационными (численными) методами: методом дихотомии, методом простой итерации, методом Ньютона, методом хорд и т.д.
Пример
Решим
уравнение
методом
простой
итерации
.
Зададим
.
Построим
график функции.
На
графике видно, что корень нашего уравнения
принадлежит отрезку
,
т.е.
– отрезок изоляции корня нашего
уравнения. Проверим это аналитически,
т.е. выполнение условий (2):
Напомним,
что исходное уравнение (1) в методе
простой итерации преобразуется к виду
и итерации осуществляются по формуле:
(3)
Выполнение
расчетов по формуле (3) называется одной
итерацией. Итерации прекращаются, когда
выполняется условие
,
где
-
абсолютная погрешность нахождения
корня, или
,
где
-относительная
погрешность.
Метод
простой итерации сходится, если
выполняется условие
для
.
Выбором функции
в формуле (3) для итераций можно влиять
на сходимость метода. В простейшем
случае
со знаком плюс или минус.
На
практике часто выражают
непосредственно из уравнения (1). Если
не выполняется условие сходимости,
преобразуют его к виду (3) и подбирают.
Представим наше уравнение в виде
(выразим
x
из уравнения). Проверим условие сходимости
метода:
для
.
Обратите внимание, что условие
сходимости выполняется не
,
поэтому мы и берем отрезок изоляции
корня
.
Попутно заметим, что при представлении
нашего уравнения в виде
,
не выполняется условие сходимости
метода:
на
отрезке
.
На графике видно, что
возрастает быстрее, чем функция
(|tg|
угла наклона касательной к
на отрезке
)
Выберем
.
Организуем итерации по формуле:
Программно организуем процесс итераций с заданной точностью:
> fv:=proc(f1,x0,eps)
> k:=0:
x:=x1+1:
while abs(x1-x)> eps do
x1:=f1(x):
print(evalf(x1,8)):
print(abs(x1-x)):
:printf("Кол. итер.=%d ",k):
end :
На
19 итерации мы получили корень нашего
уравнения
c
абсолютной погрешностью
Решим наше уравнение методом Ньютона . Итерации в методе Ньютона осуществляются по формуле:
Метод Ньютона можно рассматривать как метод простой итерации с функцией, тогда условие сходимости метода Ньютона запишется в виде:
.
В
нашем обозначении
и условие сходимости выполняется на
отрезке
,
что видно на графике:
Напомним,
что метод Ньютона сходится с квадратичной
скоростью и начальное приближение
должно быть выбрано достаточно близко
к корню.
Произведем
вычисления:
,
начальное приближение,
.
Организуем
итерации по формуле:
Программно
организуем процесс итераций с заданной
точностью.
На
4 итерации получим корень уравнения
с
Мы
рассмотрели методы решения нелинейных
уравнений на примере кубических
уравнений, естественно, этими методами
решаются различные виды нелинейных
уравнений. Например, решая уравнение
методом
Ньютона с
,
находим корень уравнения на [-1,5;-1]:
Задание
:
Решить нелинейные уравнения с точностью
0.
деления отрезка пополам (дихотомии)
простой итерации.
Ньютона (касательных)
секущих – хорд.
Варианты
заданий рассчитываются следующим
образом: номер по списку делится на 5
(
),
целая часть соответствует номеру
уравнения, остаток – номеру метода.
Решение оформляется в формате Word .
Правила ввода функции
Примеры≡ x^2/(1+x)
cos 2 (2x+π) ≡ (cos(2*x+pi))^2
≡ x+(x-1)^(2/3)
Одним из наиболее эффективных способов численного решения уравнений является метод итерации
. Сущность этого метода заключается в следующем. Пусть дано уравнение f(x)=0 .
Заменим его равносильным уравнением
Выберем начальное приближение корня x 0 и подставим его в правую часть уравнения (1). Тогда получим некоторое число
x 1 =φ(x 0). (2)
Подставляя теперь в правую часть (2) вместо x 0 число x 1 получим число x 2 =φ(x 1). Повторяя этот процесс, будем иметь последовательность чисел
x n =φ(x n-1) (n=1,2..). (3)
Если эта последовательность сходящаяся, то есть существует предел , то переходя к пределу в равенстве (3) и предполагая функцию φ(x) непрерывной найдем
Или ξ=φ(ξ).
Таким образом, предел ξ является корнем уравнения (1) и может быть вычислен по формуле (3) с любой степенью точности.
Рис. 1а Рис. 1б
Рис. 2.
|φ′(x)|>1 - расходящийся процесс
На рис.1а, 1б в окрестности корня |φ′(x)|<1 и процесс итерации сходится. Однако, если рассмотреть случай |φ′(x)|>1, то процесс итерации может быть расходящимся (см. рис.2).
Достаточные условия сходимости метода итерации
Теорема 7. Пусть функция φ(x) определена и дифференцируема на отрезке , причем все ее значения φ(x)∈ и пусть |φ′(x)|≤q<1 при x∈. Тогда процесс итерации x n = φ(x n -1) сходится независимо от начального значения x 0 ∈ и предельное значение является единственным корнем уравнения x= φ(x) на отрезке .Доказательство: Рассмотрим два последовательных приближения x n = φ(x n -1) и x n +1 = φ(x n) и возьмем их разность x n+1 -x n =φ(x n)-φ(x n-1). По теореме Лагранжа правая часть может быть представлена как
φ′(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 |
Полагая n=1,2,...
|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)
Из (4) в силу условия q<1 видно, что последовательность {x n } сходится к некоторому числу ξ, то есть , и следовательно,
(в силу непрерывности функции φ(x))
или ξ= φ(ξ) ч.т.д.
Для погрешности корня ξ можно получить следующую формулу.
Имеем x n =φ(x n-1).
Далее ξ-x n =ξ-φ(x n-1) = φ(ξ)-φ(x n-1) →
Теперь φ(x n-1)=φ(x n)-φ′(c)(x n -x n-1) →
φ(ξ)-φ(x n)+φ′(c)(x n -x n-1)
В результате получим
ξ-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)
откуда видно, что при q близком к 1 разность |ξ -x n | может быть очень большой несмотря на то что |x n -x n -1 |<ε, где ε-заданная величина. Для того, чтобы вычислить ξ с точностью ε необходимо обеспечить
. (6)
Тогда подставляя (6) в (5), получим |ξ -x n |<ε.
Если q очень мало, то вместо (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
Отсюда на основании (7) получаем
0≤|1-λM 1 |≤|1-λm 1 |≤q
Тогда выбирая λ = 1/M 1 , получим
q = 1-m 1 /M 1 < 1.
Если λ =1/f’(x), то итерационная формула x n = φ(x n -1) переходит в формулу Ньютона
x n = x n -1 – f(x n)/f’(x).
Метод итераций в Excel
В ячейку B2 заносим начало интервала a , в ячейку B3 заносим конец интервала b . Строку 4 отводим под заголовок таблицы. Сам процесс итераций организуем в ячейках A5:D5 .Процесс нахождения нулей функции методом итераций состоит из следующих этапов:
- Получить шаблон с омощью этого сервиса.
- Уточнить интервалы в ячейках B2 , B3 .
- Копировать строки итераций до требуемой точности (столбец D).
Пример
. Найти корень уравнения 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 |