Метод Ньютона и его модификации решения систем нелинейных уравнений

Федеральное агентство по образованию

Сочинский государственный университет туризма и курортного дела

Факультет информационных технологий и математики

Кафедра общей математики

Курсовая работа по дисциплине

«Численные методы»

на тему:

«Метод Ньютона и его модификации решения систем нелинейных уравнений»

Выполнила:

студентка 3 курса

группы 06-ИНФ

Лавренко М.В.

Проверил:

доцент, кандидат

педагогических наук

Иванов И.А.

Сочи 2009

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.3

1.
МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.4

ВЕКТОРНАЯ ЗАПИСЬ НЕЛИНЕЙНЫХ СИСТЕМ.5

1.2. ОСНОВНАЯ ТЕОРЕМА О СХОДИМОСТИ МЕТОДА НЬЮТОНА.7

1.3.
КРИТЕРИЙ ОКОНЧАНИЯ.8

2.
МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.11

2.1.
ОПИСАНИЕ МЕТОДА.11

2.2.
СХОДИМОСТЬ МЕТОДА.12

2.3.
ТРУДНОСТИ ИСПОЛЬЗОВАНИЯ.14

3.
МОДЕФИКАЦИЯ МЕТОДА НЬЮТОНА.15

3.1.
УПРОЩЁННЫЙ МЕТОД НЬЮТОНА.15

3.2.
ИСПОЛЬЗОВАНИЕ ФОРМУЛ ЧИСЛЕННОГО ДИФФЕРЕНЦИРОВАНИЯ.16

3.3.
МЕТОД ЛОЖНОГО ПОЛОЖЕНИЯ.17

3.4.
МЕТОД СЕКУЩИХ.17

3.5.
МЕТОД СТЕФФЕНСЕНА.18

4.
ЧИСЛЕННЫЙ ПРИМЕР. 20

5.
ЛИСТИНГ ПРОГРАММЫ НА ЯЗЫКЕ MATHCAD.. 21

ЗАКЛЮЧЕНИЕ. 23

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.24

ВВЕДЕНИЕ.

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

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

А так же коротко описываются: методы ложного положения, метод секущих, метод Стеффенсена, который чаще оказывается лучшим выбором для решения систем нелинейных уравнений нежели метод секущих или метод ложного положения.

1. МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

Знаменитый метод Ньютона является одним из наиболее эффективных методов решения самых разных нелинейных задач. Расчётную формулу метода можно получить, используя различные подходы. Рассмотрим два из них.

1) Метод касательных.

Выведем расчётную формулу метода для решения нелинейного уравнения из простых геометрических соображений. Пусть - заданное начальное приближение к корню . В точке с координатами проведём касательную к графику функции и за новое приближение примем абсциссу точки пересечения этой касательной с осью . Аналогично за приближение примем абсциссу точки пересечения с осью касательной, проведённой к графику в точке с координатами . Продолжая этот процесс далее, получим последовательность приближённой к корню .

Уравнение касательной, проведённой к графику функции в точке имеет вид:

. (1.1)

Полагая в равенстве (1.1) , замечаем, что при выполнении условия абсцисса точки пересечения касательной с осью удовлетворяет равенству:

. (1.2)

Выражая из него , получаем расчётную формулу метода Ньютона
:

, . (1.3)

Благодаря такой геометрической интерпретации этот метод часто называют методом касательных
.

ВЕКТОРНАЯ ЗАПИСЬ НЕЛИНЕЙНЫХ СИСТЕМ.

Пусть требуется решить систему уравнений

(1)

где— заданные, нелинейные (среди них могут быть и линейные)

вещественнозначные функции п
вещественных переменных . Обозначив

, ,

данную систему (2.1) можно записать одним уравнением

(2)

относительно векторной функции F
векторного аргумента х. Таким образом, исходную задачу можно рассматривать как зада­чу о нулях нелинейного отображения В этой постановке она является прямым обобщением основной задачи предыдущей главы — задачи построения методов нахождения нулей одномерных нелинейных отображений. Фактически это та же задача, только в пространствах большей размерности. Поэтому можно как заново строить методы ее решения на основе разработанных выше подходов, так и осуществлять формальный перенос выведенных для скалярного случая расчетных формул. В любом случае следует позаботиться о правомочности тех или иных операций над векторными переменными и векторными функциями, а также о сходимости получаемых таким способом итерационных процессов. Часто теоремы сходимости для этих процессов являются тривиальными обобщениями соответствующих результатов, полученных для методов решения скалярных уравнений. Однако не все результаты и не все методы можно перенести со случая п
= 1 на случай п
≥2. Например, здесь уже не будут работать методы дихотомии, поскольку множество векторов не упорядочено. В то же время, переход от n
= 1 до n
≥
2 вносит в задачу нахождения нулей нелинейного отображения свою специфику, учет которой приводит к новым методам и к различным модификациям уже имеющихся. В частности, большая вариативность методов решения нелинейных систем связана с разнообразием способов, которыми можно решать линейные алгебраические задачи, возникающие при пошаговой линеаризации данной нелинейной вектор-функции F
(
x
).

2) Метод линеаризации.

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

Пусть приближение уже получено. Представим функцию в окрестности точки по формуле Тейлора:

. (1.4)

Здесь - некоторая точка, расположенная между и . Заменяя в уравнении функцию главной линейной частью разложений (1.4), получим линейное уравнение:

. (1.5)

Принимая решение уравнения (5) за новое приближение , приходим к формуле (1.3).

1.2. ОСНОВНАЯ ТЕОРЕМА О СХОДИМОСТИ МЕТОДА НЬЮТОНА.

Теорема 1.

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

, , (1.6)

где , означающая, что метод сходится с квадратичной скоростью
.

Следствием оценки (6) является априорная оценка:

, , (1.7)

в которой .

Так как (по определению простого корня), то в силу непрерывности функции и найдётся - окрестность корня, в которой при некоторых постоянных и выполнены неравенства .

Пусть
, где . Подставляя в (1.4), получим равенство:

,

в котором . Вычитая из него равенство (1.2), имеем

.

Тогда, приравняв модули обеих частей этого равенства и используя условия ограниченности и , приходим к неравенству:

,

откуда следует справедливость оценки (1.6).

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

Приведённые в теореме 1 оценки погрешности являются априорными и их использование в практике вычислений для количественной оценки погрешности неэффективно или чаще всего невозможно.

1.3. КРИТЕРИЙ ОКОНЧАНИЯ.

На практике предпочтительнее использование простой апостериорной оценки:

, (1.8)

справедливость которой обосновывается следующим утверждением.

Теорема 2.

Пусть выполнены условия теоремы 1 и . Тогда для всех верна оценка
(8).

Из оценки (1.7) следует, что . Поэтому, применяя неравенство (6), получим цепочку неравенств:

,

из которой вытекает оценка (1.8).

Наличие оценки (1.8) позволяет сформулировать следующий практический критерий окончания итерации метода Ньютона. При заданной точности вычисления нужно вести до тех пор, пока не окажется выполнимым равенство:

. (1.9)

Пример 1.

Используя метод Ньютона, найдём с точностью положительный корень уравнения .

Для имеем . Очевидно, что , т.е. -простой корень. Возьмём начальное приближение и будем выполнять итерации метода Ньютона по формуле:

.

Результаты первых итераций с 10 знаками мантиссы приведены в табл. 1.

Табл. 1

При вычисления следует прекратить, и после округления получим .

Сравнение результатов итераций со значением показывает, что приближения содержат 1, 3, 6 верных значащих цифр соответственно. Это подтверждает отмеченный ранее факт, что при каждой итерации метода Ньютона число верных значащих цифр примерно удваивается.

Пример 2.

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

По определению, - это неотрицательная величина, удовлетворяющая равенству . Таким образом, задача сводится к вычислению положительного корня уравнения , где . Итерационная формула метода Ньютона имеет вид:

. (1.10)

2. МЕТОД НЬЮТОНА И ЕГО РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.

2.1. ОПИСАНИЕ МЕТОДА.

Обобщим метод Ньютона, изложенный в пункте 1 для решения одного нелинейного уравнения, на решение систем нелинейных уравнений. При этом будем исходить из трактовки метода Ньютона как метода линеаризации.

Предположим, что исходя из начального приближения к решению построены приближения . Заменим в системе

(*)

каждую из функций линейной частью её разложения по формуле Тейлора в точке :

.

В результате придём к системе линейных алгебраических уравнений:

,

,

. . . . . . . . . . . . . . .

,

имеющей в матричной форме записи вид:

. (2.1)

Здесь - матрица Якоби. .

Предположим, что матрица невырожденная, т.е. существует обратная матрица . Тогда система (2.1) имеет единственное решение, которое принимается за очередное приближение к решению . Таким образом, приближение удовлетворяет равенству:

, (2.2)

выражая из которого , выводим итерационную формулу метода Ньютона:

. (2.3)

Замечание.

Формула (2.3) предполагает использование трудоёмкой операции обращения матрицы, поэтому непосредственное её использование для вычисления в большинстве случаев нецелесообразно. Обычно вместо этого решают эквивалентную системе (2.2) систему линейных алгебраических уравнений:

(2.4)

относительно поправки . Затем полагают:

ign:right;">(2.5)

2.2. СХОДИМОСТЬ МЕТОДА.

Сформулируем основную теорему о сходимости метода Ньютона.

Теорема 3.

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

, .

Эта оценка означает, что метод сходится с квадратичной скоростью.

Квадратичная скорость сходимости метода Ньютона позволяет использовать простой практический критерий окончания:

. (2.6)

Пример 3.

Используя метод Ньютона, найдём с точностью решение , системы .

Возьмём , и будем вести вычисления по формулам (2.4), (2.5), в которых

, .

Результаты вычислений с шестью знаками мантиссы приведены в табл. 2.

Табл. 2

При критерий окончания выполняется и можно положить , .

2.3. ТРУДНОСТИ ИСПОЛЬЗОВАНИЯ.

Трудности использования метода Ньютона не только сохраняются, но и усугубляются. Во-первых, возникает проблема вычисления на каждой итерации матрицы из частных производных, что само по себе может оказаться весьма сложным делом. Во-вторых, обостряется проблема нахождения хорошего начального приближения. Её решить в многомерном случае гораздо труднее, чем в одномерном.

3. МОДЕФИКАЦИЯ МЕТОДА НЬЮТОНА.

Если оценивать качество метода Ньютона только по числу необходимых итераций, то следовало бы сделать вывод о том, что этот метод стоит применять всегда, когда он сходится. На практике для достижения разумной точности при выборе достаточно хорошего начального приближения требуется, как правило, 3-5 итераций.

Однако при оценке общеё трудоёмкости метода следует учитывать, что на каждой итерации требуется выполнение следующей дополнительной работы:

1) вычисление компонент вектора ;

2) вычисление компонент матрицы Якоби ;

3) решение системы линейных алгебраических уравнений (2.4).

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

3.1. УПРОЩЁННЫЙ МЕТОД НЬЮТОНА.

Заменим в расчётных формулах метода Ньютона (2.4), (2.5) матрицу , зависящую от , постоянной матрицы . В результате получим расчётные формулы упрощённого метода Ньютона
:

, (3.1)

. (3.2)

Этот метод сходится со скоростью геометрической прогрессии, если начальное приближение выбрано достаточно близким к решению , причём знаменатель прогрессии тем меньше, чем ближе к .

По сравнению с методом Ньютона число итераций, необходимое для достижения заданной точности , существенно возрастает. Тем не менее общие вычислительные затраты могут оказаться меньше. Причины этого состоят в следующем. Во-первых, вычисление матрицы Якоби производится здесь только один раз; во-вторых при использовании упрощённого метода Ньютона (3.1), (3.2) многократно решается система линейных уравнений с фиксированной матрицей и различными правыми частями. Это означает, что при решении систем (3.1) методом Гаусса возможно применение LU– разложения матрицы , которое резко уменьшает число операций, необходимых для вычисления .

3.2. ИСПОЛЬЗОВАНИЕ ФОРМУЛ ЧИСЛЕННОГО ДИФФЕРЕНЦИРОВАНИЯ.

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

Например, можно использовать следующую конечно-разностную аппроксимацию производной:

.

Параметры - это конечно-разностные шаги
.

Если в расчётных формулах метода Ньютона (2.4), (2.5) заменить матрицу аппроксимирующей её матрицей с элементами , то получим следующий итерационный метод:

, (3.3)

. (3.4)

В простейшем варианте этого метода шаги не зависят от . Отметим, что выбор величины шагов представляет собой не очень простую задачу. С одной стороны, они должны быть достаточно малыми, чтобы матрица хорошо приближала матрицу , с другой стороны, они не могут быть очень малы, та как в этом случае влияние погрешностей вычисления функций на погрешность формулы (3.3) численного дифференцирования становится катастрофическим (выполняется вычитание близких приближённых чисел).

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

3.3. МЕТОД ЛОЖНОГО ПОЛОЖЕНИЯ.

Пусть - фиксированный вектор. Положим . Тогда формулы (3.3), (3.4) определяют метод ложного положении, обладающий линейной скоростью сходимости в случае, если вектор и начальное приближённое выбраны достаточно близко к решению.

3.4. МЕТОД СЕКУЩИХ.

Можно связать задание последовательности с какой-либо сходящейся к нулю векторной последовательностью, например, с последовательность невязок или поправок . Так, полагая , где j=1,…n
, a k=1,2,
…, приходим к простейшему методу секущих — обобщению скалярного метода секущих:

, (3.5)

где

,

k
=1,2,3,… .

Этот метод является двухшаговым и требует задания двух начальных точек и . При п = 1 сходимость метода (3.5) имеет порядок . Можно рассчитывать на такую же скорость и в многомерном случае.

К методу секущих так же, как и к методу Ньютона, можно применить пошаговую аппроксимацию обратных матриц на основе метода Шульца. Расчетные формулы этой модификации легко выписать, заменив в совокупности формул ААМН (аппроксимаиионный аналог метода Ньютона) матрицу на матрицу

из (3.5).

3.5. МЕТОД
СТЕФФЕНСЕНА.

Вычисления по методу Стеффенсена производят по формулам (3.3), (3.4), где .

Замечательно то, что хотя этот метод не требует вычисления производных и в отличие от метода секущих является одношаговым, он, как и метод Ньютона, обладает свойством квадратичной сходимости. Правда, как и в методе Ньютона, его применение затруднено необходимостью выбора хорошего начального приближения.

По-видимому, для решения нелинейных систем вида метод Стеффенсена чаще кажется лучшим выбором, чем метод секущих или метод ложного положения.

Как и в одномерном случае методы секущих и Стеффенсена теряют устойчивость вблизи решения (фактически это происходит при попадании приближения в область неопределённости решения ). Поэтому при использовании этих методов важно вовремя прекратить выполнение итераций.

4. ЧИСЛЕННЫЙ ПРИМЕР

Начальное приближение:

Вектор-функция:

Матрица Якоби вектор-функции:

Вычисляем корень по формуле метода Ньютона c точностью :

k
0	0 -1	-0.841 0	-1.06 0.54 0 -2	-0.944 -0.255 0 -0.5	-0.794 -1	0.794>
1	-0.794 -1	0.295 0.63	-1.821 -0.221 -1.588 -2	-0.608 0.067 0.482 -0.553	-0.657 -0.794	0.247>
2	-0.657 -0.794	0.058 0.062	-1.48 0.12 -1.314 -1.588	-0.633 -0.048 0.524 -0.59	-0.617 -0.788	0.040>
3	-0.617 -0.788	-0.0000597 0.011	-1.441 0.159 -1.234 -1.588	-0.639 -0.064 0.497 -0.58	-0.616 -0.788	0.001=
4	-0.616 -0.788	0.000522 0.0004	-1.434 0.166 -1.232 -1.576	-0.639 -0.067 0.5 -0.582	-0.616 -0.788	0<

Ответ:

5. ЛИСТИНГ ПРОГРАММЫ НА ЯЗЫКЕ
MATHCAD

Вводим вектор функцию:

Функция iter(x,y) вычисляет следующее приближение к корню по формуле Ньютона , где

,

,

,

:

Функция norma(x,y,x1,y1) вычисляет норму между текущим и следующим приближением:

Функция Newton(x,y,eps) находит решение системы уравнений с точностью до eps:

Найдем решение заданной системы нелинейных уравнений при начальном приближении x=0, y=-1, с точностью до 0.001:

Полученное решение совпадает с рассчитанным.

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.

1.
Шикин Е. В., Чхартишвили А. Г.

Математические методы и модели в управлении: Учеб. пособие. – М.: Дело, 2000. – 440 с.

2.
Амосов А. А., Дубинский Ю. А., Копчёнова Н. В.

Вычислительные методы для инженеров: Учеб. пособие. – М.: Высш. Школа, 1994. – 544 с.

3.
Демидович Б. П., Марон И. А., Шувалова Э. З.

Численные методы анализа. 2-е изд., испр. и доп. – М.: Гос. изд-во физ .-мат. Лит., 1963. – 400 с.