Решение нелинейных уравнений методом Ньютона и методом простых итераций

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

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

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

ФГОУ СПО «Уфимский авиационный техникум»

Решение нелинейных уравнений методом Ньютона и методом простых итераций

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

Процедура подготовки и решения задачи на ЭВМ достаточно сложный и трудоемкий процесс, состоящий из 3 этапов.

В настоящей курсовой работе условие задачи дано в математической формулировке, поэтому необходимость в выполнении этапов 1 и 2 отпадает и сразу можно приступить к разработке алгоритма решения задачи на ЭВМ. Под алгоритмом понимается последовательность арифметических и логических действий над числовыми значениями переменных, приводящих к вычислению результата решения задачи при изменении исходных данных в достаточно широких пределах. Таким образом, при разработке алгоритма решения задачи математическая формулировка преобразуется в процедуру решения, представляющую собой последовательность арифметических действий и логических связей между ними. При этом алгоритм обладает следующими свойствами: детерминированностью, означающей, что применение алгоритма к одним и тем же исходным данным должно приводить к одному и том уже результату; массовость, позволяющей получать результат при различных исходных данных; результативностью, обеспечивающей получение результата через конечное число шагов.

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

Задание при обработке на ЭВМ проходит ряд шагов: компиляцию, редактирование (компоновку) и выполнение.

Обработка результатов решения задачи осуществляется с помощью ЭВМ. Выводимые результаты оформлены в виде, удобном для восприятия.

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

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

1. Теоретическая часть

Рассмотрим уравнение вида

где -- любая нелинейная или трансцендентная функция, например

Для нахождения корней уравнения (1) различают следующие два этапа.

1. Отделение корней, т.е. нахождение таких интервалов по аргументу x, внутри каждого из которых существует только один корень уравнения (1).

2. Уточнение корней заключается в применении некоторого итерационного метода, в результате которого корень уравнения (1) может быть получен с любой наперед заданной точностью ?. При этом, останавливая процесс на какой-либо конечной итерации, необходимо оценить погрешность по сравнению с точным корнем, который неизвестен.

Способы отделения корней.

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

2. Метод половинного деления.

В графическом способе строится график функции (рисунок 1) и приближенно определяются ее нули (или корни уравнения) Заключив эти нули в интервалы

Рисунок 1. Графический метод отделения корней

, на границах которых выполняются условия, i=1, 2, …, и знаки производных первого и второго порядков , на интервалах постоянны, можно утверждать, что внутри каждого из этих интервалов находится один корень уравнения (1)

Если при этом , a , то корень --

двукратный корень (точка на рисунке 1); если ,

a , то -- трехкратный корень (точка на рисунке 1) и т. д.

В методе половинного деления область определения функции делят на 2, 4, 8, 16, 32, . интервала и для каждого из них анализируют знаки функции на концах интервала; если они противоположны, то внутри интервала находится не менее одного корня; если знак первой производной на интервале постоянный, т.е. (при выполнении предыдущего условия), то внутри интервала находится точно один корень. В данном параграфе рассматриваются однократные (простые) вещественные корни нелинейных уравнений (1).

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

Для этого построим невязку, т. к.. Применим к невязке теорему Лагранжа о конечных приращениях:

Так как точное значение ? неизвестно, эту погрешность заменяют верхней оценкой:

Оценка погрешности (2) является довольно грубой. Поэтому в каждом итерационном методе уточнения корней, в силу ограничений применения метода, можно вывести свою оценку погрешности.

1.1 Метод Ньютона уточнения корней

Пусть для уравнения (1) на интервале отделен корень. В методе Ньютона функция должна удовлетворять на отрезке следующим условиям:

1) существование производных 1-го и 2-го порядков;

3)производные 1-го и 2-го порядков знакопостоянны на отрезке.

Пусть имеется значение корня на k-й итерации -- . Тогда значение корня на (k+1)-й итерации вычисляется следующим образом:

где -- шаг, который подлежит определению.

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

Положим в этом разложении линейную относительно часть равной нулю, в результате чего находим значение шага :

подставляя которое в (3) , получаем

За начальное приближение принимается один из концов отрезка [a,b], а именно

Выражения (4), (5) называют итерационным методом Ньютона (или касательных) уточнения корней нелинейного уравнения (1).

Чтобы не вычислять значение первой производной на каждой итерации, достаточно вычислить ее в точке и полученное значение подставить в выражение (4) получим

Метод (5), (6) называют модифицированным методом Ньютона. Он обладает неоспоримым преимуществом перед методом (4), (5), но сходится медленнее.

Справедлива следующая теорема.

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

Действительно, поскольку f(x) непрерывна, то взяв предел от (4) при и поменяв местами знаки предела и функции, получим

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

т.е. предельное значение является корнем уравнения (1).

Поскольку невязка равна , то из разложения в ряд Тейлора имеем выражение для невязки в виде

подставляя которое в общую погрешность приближенных методов (2) при , получаем верхнюю оценку погрешности в виде (7) , где .

Рисунок 2. Метод Ньютона

Для случая, приведенного на рисунке 2, за начальное приближение принимается , так как . На основе (7) можно записать, что , и если и , то , т.е. когда приближение имеет m верных знаков, будет иметь не менее 2m верных знаков, т. е. метод Ньютона имеет квадратичную сходимость.

Поскольку верхняя оценка (7) сложна для вычисления, на практике итерационный процесс останавливают при выполненииn условия , , где - заданная точность.

Метод Ньютона называют еще методом касательных, поскольку в этом методе на каждой итерации к графику функции f(x) проводится касательная в точке до пересечения с осью абсцисс (рисунок 2).

1.2. Метод простых итераций

Метод простых итераций уточнения корней уравнения (1) состоит в замене этого уравнения эквивалентным ему уравнением

и построении последовательности

Если не удается выразить х из уравнения (1), то эквивалентное уравнение и эквивалентную функцию можно построить, например, так:

Последовательность (9) называют методом простых итераций уточнения корней уравнения (1).

Для ответа на вопросы: сходится ли последовательность (9) и, если сходится, является ли предельное значение корнем уравнения (8), а следовательно, и уравнения (1) имеет место следующая теорема.

Теорема 2 (достаточные условия сходимости метода простых итераций). Пусть функция в эквивалентном уравнении (8) определена и дифференцируема на отрезке . Тогда, если существует число q такое, что

на отрезке [a,b], то последовательность (9) сходится к единственному корню уравнения (8) при любом начальном приближении .

Доказательство. Запишем итерационный процесс (9) на двух соседних итерациях:

Вычитая из второго выражения первое, получим

Применим к правой части выражения (11) теорему Лагранжа о конечных приращениях, поскольку по условию -- дифференцируемая функция:

Используя условия (10) теоремы, из последнего равенства получаем неравенство

на основе которого можно выписать следующую цепочку неравенств:

Тогда на основе тождества

с использованием в нем цепочки (12) получим следующую оценку:

в круглых скобках которой находится сумма геометрической прогрессии. Взяв предел от (13) при , получим выражение

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

То есть существует конечный предел последовательности (9). Обозначим его через , т.е.

Для ответа на 2-й вопрос о том, является ли предельное значение корнем уравнения (8), перейдем в (9) к пределу при и, поскольку функция

дифференцируема и, следовательно, непрерывна, знаки предела и функции можно менять местами; получим

откуда следует равенство

то есть является единственным корнем уравнения (8), а следовательно, и уравнения (1).

При ответе на 3-й вопрос о погрешности метода можно пока-

показать, что если -- неизвестный точный корень уравнения (8) и итерационный процесс остановлен на k-й итерации, то погрешность, которая допускается этим приближением, оценивается сверху выражением [1]

Если задана точность , то итерации можно остановить в случае выполнения условия, полученного из (14):

или из выражения (15) оценить минимальное количество итераций для достижения заданной точности

Неравенство (16) дает завышенное число итераций, поэтому на практике итерационный процесс останавливают при выполнении условия

Рисунок 3. Метод простых итераций в случае

Геометрическая интерпретация метода простых итераций. Из рисунка 3 видно, что , так как тангенс угла наклона касательной к графику функции меньше . Следовательно, для произвольного начального приближения в соответствии с 1-й итерацией в (9) при k= 0 определяется , которое равно значению на графике функции , а поскольку треугольник ОАВ прямоугольный и равнобедренный, то . На второй итерации в (9) при k = 1 определяется , которое равно значению на графике функции , а поскольку треугольник ОСD -- равнобедренный и прямоугольный, то CD = OD =, т.е. итерационные значения , , , . стремятся в сторону точного корня (указано стрелкой справа налево).

Рисунок 4. Метод простых итераций в случае

Из рисунка 4 видно, что итерационный процесс расходится (приближения корня , , , . стремятся от корня ).

На рисунке 5 представлен случай, . Процесс итераций сходится с двух сторон, т. е. приближения корня находятся то слева, то справа от точного корня .

Итерационный процесс (9) можно использовать и в случае, когда в эквивалентном уравнении . Для этого вернемся к исходному уравнению (1) и построим эквивалентное уравнение в виде

где берется знак минус, если , и плюс, если.

Рисунок 5. Метод простых итераций в случае ,

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

2. Постановка и решение задачи

2.1 Формулировка задачи

Применение метода Ньютона и метода простых итераций для решения уравнений (на примере вычисления ).

Графическое отделение корней

Отделить корни уравнения

Решение: уравнению соответствует эквивалентное уравнение . Если построить графики функций и , то абсциссы точек пересечения графиков этих функций дадут искомые корни данного уравнения. Из рисунка 6 видно, что уравнение имеет единственный корень принадлежащий отрезку (0;1).