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

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

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

Курсовая работа

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

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

Введение

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

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

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

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

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

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

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

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

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

, (1)

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

.

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

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

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

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

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

1. Графический.

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

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



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

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

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

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

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

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

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

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

Откуда

.

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

. (2)

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

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

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

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

2) ;

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

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

, (3)

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

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

,

.

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

,

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

(4)

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

(5)

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

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

, k = 0, 1, 2… (6)

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

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

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

, (7)

, ,

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

.

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

, откуда ,

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

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

,

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

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

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

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

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

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

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

(8)

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

(9)

где , например .

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

.

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

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

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

(10)

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

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

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

(11)

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

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

,

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

,

,

, (12)

.

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

и неравенства

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

, (13)

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

,

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

Таким образом,

.

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

.

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

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

,

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

,

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

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

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

(14)

или выражением

. (15)

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

,

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

. (16)

Неравенство (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).

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

2.2 Решение задачи методом Ньютона

Методом Ньютона с точностью уточнить корень уравнения , .

Решение.

Начальное приближение , так как ; .

на , m=12.

Формула нахождения

,

Найдем

,

Формула для нахождения погрешности

,

найдем погрешность для

,

,

так как погрешность больше точности , находим

,

найдем погрешность для

,

,

так как погрешность меньше точности , корнем уравнения будем считать

.

2.3 Решение задачи методом простых итераций

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

Решение.

Эквивалентное уравнение . Начальное приближение .

,

Формула нахождения

,

Найдем

,

Формула нахождения погрешности

,

найдем погрешность для

,

,

так как погрешность больше точности , находим

,

найдем погрешность для

,

,

так как погрешность меньше точности , корнем уравнения будем считать

Ответ: .

корень уточнение итерация

3. Программная реализация

3.1 Блок-схемы

Метод Ньютона

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

3.2 Тексты программ

Метод Ньютона

N-точность

A-начало промежутка

B-конец промежутка

M-число для проверки погрешности

X0-начальное приближение

X1-следующее приближение

F-функция

F1-первая производная функции

F2-вторая производная функции

D-погрешность

procedure TForm1.Button1Click(Sender: TObject);

var n,a,b,m,x0,x1,d:real;

function F(x:real):real;

begin F:=0;

F:=x*x*x+12*x-2;

end;

function F1(x:real):real;

begin F1:=0;

F1:=3*x*x+12;

end;

function F2(x:real):real;

begin F2:=0;

F2:=6*x;

end;

begin

d:=500;

n:=strtofloat(edit1.Text);

a:=strtofloat(edit2.Text);

b:=strtofloat(edit3.Text);

m:=12;

if F(b)*F2(b)>0

then x0:=b else x0:=a;

repeat x1:=x0-F(x0)/F1(x0); x0:=x1; d:=F(x1)/m;

until d<n;

edit5.text:= 'x = '+floattostrf(x1,fffixed, 10,8);

end;

end.

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

X0-начальное приближение

Q-правильная дробь

E-точность

X1-следующее приближение

D1-погрешность

D-переменная для вычисления погрешности

F-эквивалентное уравнение

procedure TForm1.Button1Click(Sender: TObject);

Var

x0,q,e,x1,d,d1:real;

Function F(x:real):real;

begin

F:=1/6-x*x*x/12;

end;

Begin

x0:=strtofloat(edit1.Text);

q:=0,0625;

e:=strtofloat(edit3.Text);

d:=q/(1-q);

x1:=x0;

repeat

x0:=x1;

x1:=F(x0);

d1:=abs(d*(x1-x0));

until

d1<e;

edit4.text:= 'x = '+floattostrf(x1,fffixed, 10,8);

end;

end.

3.3 Тестовый пример

Возьмем в качестве примера уравнение , корень уравнения находится в промежутке [0,5;1,5]. Корень уравнения можно вычислить аналитически, он равен 1.

Результаты работы программ на тестовом примере:

Рисунок 7. Решение методом Ньютона с точностью 0,001

Рисунок 8. Решение методом Ньютона с точностью 0,0000001



Рисунок 9. Решение методом простых итераций с точностью 0,001

Рисунок 10. Решение методом простых итераций с точностью 0,000001

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

3.4 Решение задачи с помощью ЭВМ

В результате решения поставленной задачи с помощью программ получили следующие результаты:



Рисунок 7. Программа решения методом Ньютона

Рисунок 8. Программа решения методом простых итераций

Заключение

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

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

Из вышесказанного следует, что ответ на вопрос о наилучшем численном методе решения уравнения не однозначен. Он существенно зависит от того, какую дополнительную информацию о данной функции мы имеем, в соответствие с этим, каким свойствам метода придаём большее значение.

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

Список литературы

1. Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение (пер. с англ.). М.: Мир, 2001, 575 c. ISBN 5-03-003392-0.

2. Самарский А.А., Гулин А.В. Численные методы: Учеб. пособие для вузов. -- М.: Наука. Гл. ред. физ-мат. лит., 1989. -- 432 с. ISBN 5-02-013996-3.

3. Пискунов Н.С. Дифференциальное и интегральное исчисления для вузов. -- 13-е изд. -- М.: Наука. Гл. ред. физ-мат. лит., 1985. -- 432 с.

Размещено на Allbest.ru