Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Пусть известна некоторая нелинейная зависимость вида y = f(x). Требуется определить все те значения аргумента , которые обращают функцию в нуль:
. (3.1)
Для поиска корней нелинейных уравнений, как правило (за небольшим исключением: квадратные, кубические, некоторые трансцендентные уравнения) используются итерационные методы.
Первоначально рассматриваются методы решения одного нелинейного уравнения, а затем - системы нелинейных уравнений.
Метод основан на одной из теорем математического анализа. Согласно [10], функция, непрерывная в замкнутом интервале и принимающая на концах этого интервала значения разных знаков, хотя бы один раз обращается в нуль внутри интервала.
Пусть функция f(x) непрерывна на отрезке . Процедура метода заключается в последовательном сокращении длины отрезка для локализации корня уравнения (3.1). Первоначально проверяются значения заданной функции на концах отрезка. В случае, если
,
один из концов отрезка является искомым корнем уравнения.
Пусть на концах отрезка значения функции имеют разные знаки, то есть имеет место соотношение
.
Вычисляется значение аргумента в середине отрезка, , и вычисляется значение функции в этой точке. Далее сравниваются знаки функции в точке и, например, в левой точке отрезка.
Если имеет место соотношение (рис. 3.1), то корень следует искать на отрезке . В противном случае - корень разыскивается на отрезке . В результате выполненной операции исходный отрезок сократился вдвое.
f(x1)
f(x3) f(x2)
f(x4)
x0 x3 x2 x1
x4
f(x0)
Рис. 3.1. Схема метода половинного деления
Далее, в зависимости от ситуации, отрезок вновь делится пополам,
и так далее.
Для прекращения вычислительной процедуры применяются различные критерии:
- если функция достаточно “пологая”, имеет смысл использовать условие (рис.3.2a)
;
- если функция “круто” меняет свое значение, целесообразно применять условие (рис.3.2b)
.
a b
Рис. 3.2. Частные случаи поиска корня нелинейного уравнения
В случае, если заранее неизвестен характер “поведения” функции, имеет смысл использовать одновременно оба условия для прекращения итерационного процесса.
Этот метод заключается в замене уравнения (3.1) эквивалентным ему уравнением вида
. (3.2)
После этого строится итерационный процесс
(3.3)
при некотором заданном значении . Для приведения выражения (3.1) к требуемому виду (3.2) можно воспользоваться простейшим приемом:
Если в выражении (3.2) положить , можно получить стандартный вид итерационного процесса для поиска корней нелинейного уравнения:
.
Пример 3.1. Решим уравнение cos(x) - x = 0. Представим это уравнение в виде
.
Результаты расчетов приведены в табл. 3.1. Ход итерационного процесса отражен на рис. 3.3.
Таблица 3.1
Результаты итерационного вычисления корня уравнения cos(x) - x = 0
|
Номер итерации |
Аргумент x |
|
1 |
0 |
|
2 |
1,0 |
|
3 |
0,540302306 |
|
4 |
0,857553216 |
|
5 |
0,654289791 |
|
6 |
0,793480359 |
|
7 |
0,701368774 |
|
8 |
0,763959683 |
|
9 |
0,722102425 |
|
10 |
0,750417762 |
|
... |
... |
|
30 |
0,739078886 |
|
31 |
0,739089341 |
Корень уравнения (с абсолютной погрешностью не более ) равен 0,739085133.
Рис. 3.3. Поиск корня нелинейного уравнения cos(x) - x = 0
Рассмотрим отрезок длиной 2r с центром в точке a: .
Теорема 3.1. Если функция на отрезке А удовлетворяет условию Липшица3 с константой 0 < С < 1, причем
, (3.4)
то уравнение (3.2) имеет на отрезке А единственное решение , метод простой итерации сходится к при любом и имеет место оценка
. (3.5)
Доказательство.
Докажем “по индукции”, что определяемые в соответствии с формулой (3.2) величины .
по условию теоремы.
Пусть ; покажем, что и .
В силу имеем
то есть .
Теперь оценим разность получаемых решений для произвольного n:
.
Отсюда получаем
.
Для двух произвольных значений (для определенности положим p > q) на основании этого соотношения имеем
При выводе последнего соотношения использована формула для суммы членов геометрической прогрессии со знаменателем С, а также условие, что 0 < C < 1, и тем более .
Очевидно, что при имеет место
,
и в соответствии с признаком Больцано - Коши4
.
Переходя к пределу в соотношении , в силу непрерывности функции получаем:
,
то есть - решение уравнения (3.2).
Теперь покажем, что получаемое решение единственно. В самом деле, пусть - два различных решения уравнения (3.2). Тогда
,
что может иметь место при условии 0 < C < 1 лишь в случае .
Оценим погрешность метода простой итерации после выполнения N итераций:
,
откуда получаем:
.
Что и требовалось доказать.
Следствие 1. Если , а также имеет место соотношение
,
то уравнение (3.2) имеет единственное решение, метод простых итераций сходится и имеет место оценка (3.5).
Действительно, согласно теореме Лагранжа5,
,
то есть в качестве константы условия Липшица можно принять
.
В этом случае условия теоремы (3.1) выполняются и все ее утверждения имеют место.
Для поиска корней уравнения (3.1) в окрестности решения выберем точку x и разложим функцию f(x) в ряд Тейлора7 возле этой точки:
.
Отсюда следует приближенное равенство
,
которое с учетом
позволяет получить выражение
,
приводящее к итерационному процессу следующего вида:
. (3.6)
Очевидно, что метод Ньютона можно рассматривать как вариант метода простых итераций, при условии .
Геометрическая иллюстрация итерационного процесса метода Ньютона приведена на рис. 3.4, из которого понятно, что каждое следующее приближение может быть определено из геометрических построений:
.
f(x)
f(x0)
f(x1)
f(x2)
x3 x2 x1 x0 x
Рис. 3.4. Геометрический смысл процедуры метода Ньютона
Пример 3.2. Требуется определить корни уравнения .
Согласно рассмотренному методу Ньютона строится итерационная процедура
.
Поскольку
,
.
Таким образом, применение процедуры метода Ньютона к заданному уравнению приводит к вычислительному процессу
.
Для а=2 “точное” решение . Результаты расчетов приведены в табл. 3.2.
Таблица 3.2
Последовательность получения приближенного решения
уравнения методом Ньютона
|
Номер итерации |
Приближения решения |
|
|
1 |
2,0 |
-10,0 |
|
2 |
1,5 |
-5,1 |
|
3 |
1,416666667 |
-2,746078431 |
|
4 |
1,414215686 |
-1,737194874 |
|
5 |
1,414213562 |
-1,444238095 |
|
6 |
1,4142135624 |
-1,414525655 |
|
7 |
1,4142135624 |
-1,414213597 |
|
8 |
1,4142135624 |
-1,4142135624 |
Теорема 3.2. Пусть выполнены следующие предположения:
- - корень уравнения f(x) = 0;
- первая производная ;
- вторая производная непрерывна в А;
- константа , где .
Тогда, если , то метод Ньютона сходится, причем
. (3.7)
Доказательство.
Для оценки погрешности решения воспользуемся формулой Тейлора для функции f(x) возле точки :
.
В силу получаем соотношение
.
С другой стороны, согласно методу Ньютона,
.
Отсюда,
, (3.8)
то есть имеет место квадратичная сходимость.
Пусть . Из формулы (3.8) получаем
,
то есть оценка (3.7) выполнена для N=1. Допустим, что формула (3.7) верна для произвольного q. С учетом условия С<1, имеем
,
то есть , а следовательно определены
.
Из соотношения (3.8) получаем
Согласно (3.7)
.
С учетом этого, из предыдущего выражения следует:
Но это как раз и означает, что формула (3.7) справедлива при N = q+1.
В силу C<1 из выражения (3.7) следует сходимость метода Ньютона:
,
что и требовалось доказать.
Одна из модификаций метода Ньютона заключается в том, что производную от функции f(x) определяют лишь один раз для начальной точки итерационного процесса (рис. 3.5 а):
.
При таком способе решения уравнения скорость сходимости уменьшается, иногда существенно. Эту модификацию метода целесообразно применять в том случае, когда вычисление производной связано с большими затратами вычислительных ресурсов (времени, оперативной памяти), либо когда аналитический вид функции f(x) неизвестен, что часто бывает при решении прикладных инженерных проблем. Кроме того, практически всегда можно подобрать начальное значение таким образом, что , то есть не будет аварийной остановки вычислительного алгоритма.
Другая модификация (метод секущих) заключается в замене производной функции f(x) ее разностным аналогом (рис. 3.5 b):
.
В этом случае получена двухточечная схема, то есть для начала расчетов необходимо задать две начальные точки .
Пример 3.3. Определить корни уравнения
.
Точное решение этого уравнения: .
Для использования метода простых итераций представим это уравнение в форме (3.2):
Для проверки условий сходимости в качестве константы условия Липшица возьмем
.
Очевидно, что 0 < C < 1 на интервале (-2, 2), r = 2. Центр интервала a = 0. При этих параметрах условие теоремы
не выполняется, чем объясняется отсутствие сходимости решения, например, при начальном приближении .
Поскольку
,
алгоритм метода Ньютона в соответствии с выражением (3.6) записывается в виде:
.
Результаты вычисления по обоим алгоритмам приведены в табл. 3.3.
x5 x4 x3 x2 x1 x0 x3 x2 x1 x0 a b
Рис. 3.5. Схемы модифицирования метода Ньютона:
a - с начальным значением касательной; b - метод секущих
Возможно, что на заданном отрезке может оказаться несколько корней. В этом случае итерационный процесс позволит вычислить какой-то один корень уравнения. Для отделения корней в некоторых случаях можно воспользоваться следующим приемом.
Пусть найден корень . Построим функцию
.
Рассмотрим . Вычисление этого предела приводит к неопределенности типа . Согласно правилу Лопиталя8 [10],
при условии ограниченности производной функции, то есть в случае . При отсутствии кратных корней новая функция и “слева”, и “справа” от точки будет иметь один и тот же знак. После нахождения следующего корня строится функция
,
и так далее.
Таблица 3.3.
Решение уравнения методами Ньютона и простых итераций при различных начальных приближениях
|
Номер итерации |
Метод простых итераций |
Метод Ньютона |
|||
|
1 |
0,5 |
2,5 |
4,0 |
0,0 |
4,0 |
|
2 |
0,821 |
2,3125 |
4,75 |
0,75 |
3,25 |
|
3 |
0,915039 |
2,0869 |
6,3906 |
0,975 |
3,025 |
|
4 |
0,9593241 |
1,8388 |
10,96 |
0,9996951 |
3,0003048 |
|
5 |
0,9800756 |
1,5953 |
30,78 |
0,9999999 |
3,0 |
|
6 |
0,990137 |
1,3862 |
273,6 |
1,0 |
- |
|
7 |
0,9950928 |
1,2304 |
14115,4 |
- |
- |
|
8 |
0,9975524 |
1,1285 |
49811068 |
- |
- |
|
9 |
0,9987777 |
1,0684 |
- |
- |
|
|
10 |
0,9993892 |
1,0354 |
- |
- |
|
|
11 |
0,9996947 |
1,0180 |
- |
- |
|
|
12 |
0,9998473 |
1,0091 |
- |
- |
1 Дополнительно методы решения нелинейных уравнений рассматриваются в разделе, посвященном интерполяции функций.
2 Встречаются иные названия этого метода - метод бисекции, дихотомии.
3Липшиц Рудольф Отто Сигизмунд [14.5.1832 - 7.10.1903] - немецкий математик. С 1864 года является профессором Боннского университета. В 1900 году избран членом - корреспондентом Парижской академии наук.
Функция удовлетворяет условию Липшица на отрезке [a, b], если - константа, [8].
4Больцано Бернард [5.10.1781 - 18.12.1848] - чешский математик, философ, теолог. В 1800 году закончил философский, а в 1805 - теологический факультеты Пражского университета. В этом же университете с 1805 года возглавлял кафедру истории религии, откуда был уволен в 1820 году за вольнодумство и лишен права публичных выступлений. После этого занимался исследованием в области логики и математики.
Коши Огюстен Луи [21.8.1789 - 23.5.1857] - французский математик. В 1807 году окончил Политехническую школу, в 1810 году - Школу мостов и дорог в Париже. С 1810 по 1813 годы работал инженером в Шербурге. С 1816 года был избран членом Парижской академии наук. С 1816 по 1830 год преподавал в Политехнической школе и в Коллеж де Франс. С 1831 года стал иностранным почетным членом Петербургской академии наук. В 1848 году начал преподавать в Парижском университете.
Признак сходимости числовой последовательности Больцано-Коши [8]: для того, чтобы последовательность вещественных чисел имела конечный предел, необходимо и достаточно, чтобы при .
5 Лагранж Жозеф Луи [25.11.1736 - 10.4.1813] - французский математик и механик. В 1755 году стал профессором Туринской артиллерийской школы. В 1759 году был избран членом Берлинской академии наук. С 1766 года был директором Математического класса Берлинской академии наук, с 1772 года - членом Парижской академии наук, с 1776 года - иностранным почетным членом Петербургской академии наук. В 1795 году стал профессором Парижской Нормальной школы, с 1797 года - профессором Политехнической школы.
Теорема Лагранжа [10]: если функция f(x) непрерывна в замкнутом интервале и дифференцируема во всех его внутренних точках, то внутри этого интервала существует хотя бы одна точка , для которой .
6 Ньютон Исаак [4.1.1643 - 31.3.1727] - английский физик и математик. В 1655 году начал учебу в Грантемской школе, в 1661 году поступил в Тринити - колледж Кембриджского университета. В 1668 году ему была присвоена степень магистра. С 1669 по 1701 годы занимал почетную люкасовскую физико-математическую кафедру. С 1672 года был членом Лондонского королевского общества, президентом которого стал в 1703 году. В 1695 году получил должность смотрителя Монетного двора. В 1699 году был избран иностранным почетным членом Петербургской академии наук. В 1705 году за научные труды был возведен в дворянское звание.
7 Тейлор Брук [18.8.1685 - 29.12.1731] - английский математик. В 1712 году был избран членом Лондонского королевского общества.
8 Лопиталь Гийом Франсуа Антуан де [1661 - 1704] - французский математик, автор первого печатного учебника по дифференциальному исчислению.
PAGE 73