Исследование различных явлений или процессов математическими методами осуществляется с помощью математической модели. Математическая модель представляет собой формализованное описание исследуемого объекта посредством систем линейных, нелинейных или дифференциальных уравнений, систем неравенств, определенного интеграла, многочлена с неизвестными коэффициентами и т. д. Математическая модель должна охватывать важнейшие характеристики исследуемого объекта и отражать связи между ними.
После того, как математическая модель составлена, переходят к постановке вычислительной задачи. При этом устанавливают, какие характеристики математической модели являются исходными (входными)данными, какие - параметрами модели, а какие - выходными данными. Проводится анализ полученной задачи с точки зрения существования и единственности решения.
На следующем этапе выбирается метод решения задачи. Во многих конкретных случаях найти решение задачи в явном виде не представляется возможным, так как оно не выражается через элементарные функции. Такие задачи можно решить лишь приближенно. Под вычислительными (численными) методами подразумеваются приближенные процедуры, позволяющие получать решение в виде конкретных числовых значений. Вычислительные методы, как правило, реализуются на ЭВМ. Для решения одной и той же задачи могут быть использованы различные вычислительные методы, поэтому нужно уметь оценивать качество различных методов и эффективность их применения для данной задачи.
Затем для реализации выбранного вычислительного метода составляется алгоритм и программа для ЭВМ. Современному инженеру важно уметь преобразовать задачу к виду, удобному для реализации на ЭВМ и построить алгоритм решения такой задачи.
В настоящее время широко используются как пакеты, реализующие наиболее общие методы решения широкого круга задач (например, 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 .
Правила ввода функции
Примеры≡ 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 |
Решение нелинейных уравнений
Пусть требуется решить уравнение
Где
– нелинейная непрерывная функция.
Методы решения уравнений делятся на прямые и итерационные. Прямые методы – это методы, позволяющие вычислить решение по формуле (например, нахождение корней квадратного уравнения). Итерационные методы – это методы, в которых задается некоторое начальное приближение и строится сходящаяся последовательность приближений к точному решению, причем каждое последующее приближение вычисляется с использованием предыдущих
Полное решение поставленной задачи можно разделить на 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
(
),
целая часть соответствует номеру
уравнения, остаток – номеру метода.
Задание:
1) Используя метод итераций, решить систему
2) Используя метод Ньютона, решить систему
нелинейных уравнений с точностью до 0,001.
Задание №1Используя метод итераций, решить систему нелинейных уравнений с точностью до 0,001.
Теоретическая часть.
Метод итераций э то способ численного решения математических задач. Его суть – нахождение алгоритма поиска по известному приближению (приближенному значению) искомой величины следующего, более точного приближения. Применяется в случае, когда последовательность приближений по указанному алгоритму сходится.
Данный метод называют также методом последовательных приближений, методом повторных подстановок, методом простых итераций и т.п.
Метод Ньютона , алгоритм Ньютона (также известный как метод касательных) - это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643-1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства. Обоснование
Чтобы численно решить уравнение методом простой итерации, его необходимо привести к следующей форме: , где - сжимающее отображение.
Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Решение данного уравнения ищут в виде , тогда:
В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна , окончательная формула для такова:
С учётом этого функция определяется выражением:
Эта функция в окрестности корня осуществляет сжимающее отображение, и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:
.
Варианты заданий
№1. 1)
2)
№2. 1)
2)
№3. 1)
2)
№4. 1)
2)
№5. 1)
2)
№6. 1)
2)
№7. 1)
2)
№8. 1)
2)
№9. 1)
2)
№10.1)
2)
№11.1)
2)
№12.1)
2)
№13.1)
2)
№14.1)
2)
№15.1)
2)
№16.1)
2)
№17.1)
2)
№18.1)
2)
№19.1)
2)
№20.1)
2)
№21. 1)
2)
№22. 1)
2)
№23. 1)
2)
№24. 1)
2)
№25. 1)
2)
№26. 1)
2)
№27. 1)
2)
№28. 1)
2)
№29. 1)
2)
№30. 1)
2)
Образец выполнения задания
№1. 1)
2)
Пример решения системы нелинейных уравнений методом итераций
Перепишем данную систему в виде:
Отделение корней производим графически (рис.1). Из графика видим, что система имеет одно решение, заключенное в области D: 0<х <0,3;-2,2<y <-1,8.
Убедимся в том, что метод итераций применим для уточнения решения системы, для чего запишем ее в следующем виде:
Так как ,то имеем в области D
+ = ;
+ =
Таким образом, условия сходимости выполняются.
Таблица №2
п | ||||||
0,15 | -2 | -0,45 | -0,4350 | -0,4161 | -0,1384 | |
0,1616 | -2,035 | -0,4384 | -0,4245 | -0,4477 | -0,1492 | |
0,1508 | -2.0245 | -0,4492 | -0,4342 | -0,4382 | -0,1461 | |
0.1539 | -2,0342. | -0,4461 | -0.4313 | -0,4470 | -0,1490 | |
0.1510 | -2,0313 | -0,4490 | -0,4341 | -0,4444 | -0.1481 | |
0,1519 | -2,0341 | -0,4481 | -0,4333 | -0,4469 | -0,1490 | |
0,1510 | -2.0333 | -0.449 | -0,4341 | -0.4462 | -0,1487 | |
0.1513 | -2.0341 | -0,4487 | -0,4340 | -0,4469 | -0.1490 | |
0.1510 | -2,0340 |
За начальные приближения принимаем х о =0,15, у 0 = -2.
(таб.№2). Тогда ответ запишется:
Пример решения системы нелинейных уравнений методом Ньютона
Отделение корней производим графически (рис.2). Для построения графиков функций составим таблицу значений функций и , входящих в первое и второе уравнения (табл. I).
Значения для x можно брать исходя из следующих условий: из первого уравнения 1≤1,2х+0,4≤1 , т.е. 1,16≤х≤0,5 ; из второго уравнения , т.е. . Таким образом, .
Система имеет два решения. Уточним одно из них, принадлежащее области D: 0,4<x <0,5;
0,76<y <0,73. За начальное приближение примем Имеем:
Таблица №3
x | -1,1 | -1 | -0,8 | -0,6 | -0,2 | -0,4 | 0,2 | 0,4 | 0,5 | |
х 2 | 1.21 | 0,64 | 0,36 | 0,04 | 0,16 | 0,04 | 0.16 | 0,25 | ||
0,8 х 2 | 0,97 | 0,8 | 0,51 | 0,29 | 0,032 | 0,13 | 0,032 | 0,13 | 0,2 | |
1 -0,8 х 2 | 0,03 | 0,2 | 0,49 | 0,71 | 0,97 | 0,87 | 0,97 | 0.87 | 0,8 | |
0,02 | 0,13 | 0,33 | 0,47 | 0,65 | 0,58 | 0,67 | 0,65 | 0,58 | 0.53 | |
±0,14 | ±0,36 | ±0,57 | ±0,69 | ±0,81 | ±0,76 | ±0,82 | ±0.81 | ±0,76 | ±0.73 | |
1,2x | -1,32 | -1,2 | -0,9б" | -0,72 | -0,24 | -0,48 | 0,24 | 0,48 | 0,6 | |
0,4+1,2x | -0,92 | -0,8 | -0,56 | -0,32 | 0,16 | -0,08 | 0,4 | 0,64 | 0.88 | |
2x-y | -1.17 | -0,93 | -0,59 | -0,33 | 0,16 | -0,08 | 0,41 | 0,69 | 2.06 1,08 | 1,57 |
-1,03 | -1,07 | -1,01 | -0,87 | -0,56 | -0,72 | -0,41 | -0,29 | -1,26 -1,28 | -0.57 |
Уточнение корней проводим методом Ньютона:
где ; ;
;
;
Все вычисления производим по таблице 3
Таблица 3 | 0,10 | 0,017 | -0,0060 | 0,0247 | -0,0027 | -0,0256 | 0,0001 | 0,0004 | ||||||||
0,2701 | 0,0440 | -0,0193 | 0,0794 | -0,0080 | -0,0764 | -0,0003 | 0,0013 | |||||||||
2,6197 | 3,2199 | 2,9827 | 3,1673 | |||||||||||||
-0,0208 | -2,25 | 0,1615 | -2,199 | 0,1251 | -2,1249 | 0,1452 | -2,2017 | |||||||||
-1,1584 | 0,64 | -1,523 | 0,8 | -1,4502 | 0,7904 | -1,4904 | 0,7861 | |||||||||
0,1198 | -0,0282 | -0,0131 | 0,059 | -0,0007 | -0,0523 | -0,0002 | 0,0010 | |||||||||
0,9988 | 0,0208 | 0,9869 | -0,1615 | 0,9921 | -0,1251 | -0,9894 | -0,1452 | |||||||||
0,55 | 0,733 | 1,6963 | 1,7165 | |||||||||||||
0,128 | 0,8438 | 0,2 | 0,8059 | 0,1952 | 0,7525 | 0,1931 | 0,8079 | |||||||||
0,4 | 0,75 | 0,50 | -0,733 | 0,4940 | -0,7083 | 0,4913 | -0,7339 | 0,4912 | -0,7335 | Ответ: x ≈0,491 y ≈ 0,734 | ||||||
n | ||||||||||||||||
Контрольные вопросы
1) Представьте на графике возможные случаи решения системы двух нелинейных уравнений.
2) Сформулируйте постановку задачи о решении системы n-линейных уравнений.
3) Приведите итерационные формулы метода простой итерации в случае системы двух нелинейных уравнений.
4) Сформулируйте теорему о локальной сходимости метода Ньютона.
5) Перечислите трудности, возникающие при использовании метода Ньютона на практике.
6) Объяснить каким образом можно модифицировать метод Ньютона.
7) Изобразите в виде блок-схем алгоритм решения систем двух нелинейных уравнений методами простой итерации и Ньютона.
Лабораторная работа №3
Метод простой итерации, называемый также методом последовательного приближения, - это математический алгоритм нахождения значения неизвестной величины путем постепенного ее уточнения. Суть этого метода в том, что, как видно из названия, постепенно выражая из начального приближения последующие, получают все более уточненные результаты. Этот метод используется для поиска значения переменной в заданной функции, а также при решении систем уравнений, как линейных, так и нелинейных.
Рассмотрим, как данный метод реализуется при решении СЛАУ. Метод простой итерации имеет следующий алгоритм:
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
Результаты, полученные при подстановке найденных значений в исходные уравнения, полностью удовлетворяют условиям уравнения.
Как мы видим, метод простой итерации дает довольно точные результаты, однако для решения этого уравнения нам пришлось потратить много времени и проделать громоздкие вычисления.