Нахождение корня уравнения методом касательных и комбинированным методом

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

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

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

Нахождение корня уравнения методом касательных  и комбинированным методом

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

Введение

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

1. Постановка задачи (задача, которую предстоит решать на ЭВМ, формулируется пользователем или получается им в виде задания).

2. Математическая формулировка задачи.

3. Разработка алгоритма решения задачи.

4. Написание программы на языке программирования.

5. Подготовка исходных данных.

6. Ввод программы и исходных данных в ЭВМ.

7. Отладка программы.

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

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

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

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

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

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

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

Данная курсовая работа состоит из трех частей: в первой части (теоретической) содержатся краткие описания методов, во второй части (практической) содержатся формулировка задачи и ее решение требуемыми методами, третья часть (программная) включает в себя блок-схемы алгоритмов, тексты (листинги) программ на языке Delphi, тестовый пример и результат его решения, а также результат решения поставленной задачи.

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

1.1    Краткое описание метода касательных

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

Этот метод применяется, если уравнение имеет корень, и выполняются следующие условия: 1)  - функция принимает значения разных знаков на концах отрезка [a;b]; 2) производные  и  сохраняют знак на отрезке (т.е. функция  либо возрастает, либо убывает на отрезке , сохраняя при этом направление выпуклости).

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

Рисунок 1. Касательная к функции

Пусть уравнение F(x)=0 имеет единственный корень на промежутке (a;b), преобразуем его к равносильному уравнению x=x-j(x)*F(x), где F(x) - любая функция и не обращающаяся в 0, пусть . Тогда рекуррентное соотношение для итерационной последовательности будет иметь вид:

Достоинства метода: простота, быстрота сходимости.

Недостатки метода: вычисление производной и трудность выбора начального положения.

1.2    Краткое описание комбинированного метода

При решении уравнений часто комбинируют методы хорд и Ньютона. Если график функции y=f(x) обращён вогнутостью вверх, то находят точки а₁ и х₁ по формулам:

(1)

 (2)

Если же график функции y=f(x) обращён вогнутостью вниз, то точку а₁ находят по формуле (1), а точку х₁ - по формуле:

(3)

Как видно из рисунка 2 а) и б), корень x уравнения f(x)=0 лежит обычно между полученными точками а₁ и х₁. Применяя снова к этим точкам формулы метода хорд и метода Ньютона, получают новую пару точек а₂ и х₂ и т. д.

Таким путём получают две последовательности точек а₁, а₂, а₃, …, a_n, … и x₁, x₂, x₃, … , x_n, …, приближаются с разных сторон к искомому корню x. Преимущество описанного метода состоит в том, что при нём получаются приближённые значения как с избытком так и с достатком.

Рисунок 2. Положение корня

а) Первое возможное положение корня б) Второе возможное положение корня

Условия применения метода:

1),

) и  сохраняют знак на отрезке ,

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

Схема решения уравнения методом хорд и касательных:

1.      Вычислить значения функции  и .

.        Проверить выполнение условия . Если условие не выполняется, то неправильно выбран отрезок .

.        Найти производные  и .

.        Проверить постоянство знака производных на отрезке . Если нет постоянства знака, то неверно выбран отрезок .

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

.        Приближения корней находятся:

а) по методу касательных:

,

б) по методу хорд:

.

.        Вычисляется первое приближение корня: .

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

Если условие не выполняется, то нужно продолжить применение метода по схеме 1-8.

В этом случае отрезок изоляции корня сужается и имеет вид . Приближённые значения корня находятся по формулам:

и.

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

·        Комбинированный метод наиболее трудоемок.

·        Метод, как и метод Ньютона не всегда сходится

·        Комбинированный метод сходится быстрее всех ранее рассмотренных, (если он сходится).

касательный хорда корень уравнение

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

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

Применение метода касательных и комбинированного метода для решения нелинейных уравнений (на примере уравнения 0,1x²-xln(x)=0)

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

Уравнению 0,1x²-xln(x)=0 соответствует эквивалентное уравнение 0,1x=ln(x). Если построить графики функций y₁=0,1x и y₂=ln(x), то абсциссы точек пересечения графиков этих функций дадут искомые корни данного уравнения. Из рисунка 3 видно, что корень уравнения лежит на промежутке [1;2].

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

f(a)=f(1)=0,1*1² -1*ln(1)=0,1>0,(b)=f(2)= 0,1*2² -2*ln(2)= -0,98629<0

2.      Проверим выполнение условия: f(a)*f(b)=0,1*(-0,98629)<0 - условие выполняется.

.        Найдем производные:

f’(x)=(0,1x² - xln(x))’=0,2x-1+ln(x),

f’’(x)=(0,2x-1+ln(x))’=0,2+1/x

4.      На отрезке [1;2] производные f’(x)<0 и f’’(x)>0, т.е. сохраняют знак, следовательно, условие выполняется.

.        Выберем значение x₀ для метода касательных. Т.к. f’’(x)>0 и f(1)>0, то x₀=1.

.        Итерационная формула метода Ньютона будет такой:

.        Применяя эту формулу, последовательно находим:

Так что x=1,118 с точностью ε = 0,001. Как мы видим, значение корня с нужной нам точностью было получено на четвертом шаге. (Пятый шаг понадобился для того, чтобы можно было убедиться, что с нужной нам точностью значение перестало изменяться).

2.3    Решение задачи комбинированным методом

1.      Вычислим значения функции 0,1x²-xln(x)=0 на концах отрезка:

f(a)=f(1)=0,1*1² -1*ln(1)=0,1>0,(b)=f(2)= 0,1*2² -2*ln(2)= -0,98629<0

2.      Проверим выполнение условия: f(a)*f(b)= 0,1*(-0,98629)<0 - условие выполняется.

.        Найдем производные:

f’(x)=(0,1x² - xln(x))’=0,2x-1+ln(x),

f’’(x)=(0,2x-1+ln(x))’=0,2+1/x

4.      На отрезке [1;2] производные f’(x)<0 и f’’(x)>0, т.е. сохраняют знак, следовательно, условие выполняется.

.        Выберем значение x₀ для метода касательных. Т.к. f’’(x)>0 и f(1)>0, то x₀=1.

.        Найдем приближения корня:

По методу касательных:

По методу хорд:

7.      Найдём первое приближение корня:

.        Проверим выполнение условия: > 0,001 - условие не выполняется, значит нужно продолжить вычисления.

.        Отрезок изоляции корня имеет вид: x [;].

10.    Продолжим уточнение корня по схеме. Для этого найдём значения функции на концах суженного отрезка:

f(1,125) = -0,005943415,(2,0356) = -1,032518641

.        Возьмем x₁₁=1,125 для метода касательных

.        Вычислим значение производной:

13.    f’(x₁₁)= f’(1,125)=-0,65722

.       
Найдём новые значения концов отрезка изоляции:

.        Найдём второе приближение корня:

.        Проверим выполнение условия:  >0,001- неравенство неверное, значит необходимо продолжить вычисления.

.        Отрезок изоляции корня имеет вид: x[1,1159; 1,1302]

.        Вычислим значения функции:

f(1,1159)=0,002152287,(1,1302)=-0,010595182

.        Условие f(1,1159)* f(1,1302)<0 выполняется

.        Так как f’’(x)>0 и f(1,1159)>0, то для метода касательных x₂₁=1,1159

.        Вычислим производную: f’(x₂₁)= f’(1,1159)=-0,66716

.        Вычислим:

Найдём третье приближение корня:

.        Проверим выполнение неравенства:  < 0,001 - условие выполняется, значит, цель достигнута.

.        Следовательно,  - приближённое значение корня с точностью до 0,0001.

Ответ:

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

.1 Блок-схемы алгоритмов

Блок-схема алгоритма к методу касательных

Блок-схема алгоритма к комбинированному методу

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

Текст программы метода касательных на языке Delphi

unit Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;= class(TForm): TButton;: TLabel;: TLabel;: TLabel;: TEdit;: TLabel;: TLabel;: TEdit;: TLabel;: TEdit;: TEdit;Button1Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TForm1;

{$R *.dfm}TForm1.Button1Click(Sender: TObject);f(x:real):real;{Исходная функция}:=0.1*sqr(x)-x*ln(x);; f1(x:real):real;{Первая производная функции}

begin:=0.2+1/x;;

var a,b,x,t,eps:real;

a:=strtofloat(edit1.Text); {Преобразует числовую строку в значение с плавающей запятой}

b:= strtofloat(edit2.Text);:=strtofloat(edit3.Text);f(a)*f2(a)>=0 then x:=a else x:=b; {Выбор начального приближения}:=f(x)/f1(x); :=x-t;abs(t)<=eps;4.text:= 'Ответ: корень = '+floattostrf(x,fffixed, 10,6); {Преобразует значение с плавающей запятой в строку};.

Текст программы комбинированного метода на языке Delphi:

unit Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;= class(TForm): TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TEdit;: TEdit;: TButton;: TEdit;: TLabel;: TEdit;Button1Click(Sender: TObject);

{ Private declarations }

{ Public declarations };Form1: TForm1;

{$R *.dfm}TForm1.Button1Click(Sender: TObject);f(x:real):real;{Исходная функция}:=0.1*sqr(x)-x*ln(x);; f1(x:real):real;{Первая производная функции}

begin:=0.2*x-1+ln(x);; f2(x:real):real;{Вторая производная функции}

begin:=0.2+1/x;;a,b,e,e1,x0,x11,x12:real;

a:=strtofloat(edit1.Text); {Преобразует числовую строку в значение с плавающей запятой}

b:= strtofloat(edit2.Text);:=strtofloat(edit3.Text);f(a)*f2(a)>=0 then x0:=a else x0:=b; {Выбор начального приближения}11:=x0-f(x0)/f1(x0); {Вычисление по методу Ньютона}

x12:=a-((b-a)*f(a)/(f(b)-f(a))); {Вычисление по комбинированному методу}

e1:=(x11+x12)/2; {Приближение корня}

while abs(e1-x11)>e do {Проверяется выполнение условия}

begin:=x11;:=x12;:=a-f(a)/f1(a);:=a-((b-a)*f(a)/(f(b)-f(a)));:=(x11+x12)/2;;.text:='Îòâåò: êîðåíü = '+floattostrf(x11,fffixed, 10,6); {Преобразует значение с плавающей запятой в строку}

end;;.

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

В качестве тестового примера рассмотрим линейное уравнение x³ - 1=0, корень которого равен 1.

На рисунке 5 представлено решение примера методом касательных.

Рисунок 5. Решение уравнения методом касательных

На рисунке 6 - решение тестового примера комбинированным методом.

Рисунок 6. Решение уравнения комбинированным методом

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

На рисунке 7 представлен результат работы программы для метода касательных.

Рисунок 7. Результат работы программы для метода касательных на языке Delphi

На рисунке 8 - результат работы программы для комбинированного метода.

Рисунок 8. Результат работы программы для комбинированного метода на языке Delphi

Заключение

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

При оценке эффективности численных методов существенное значение имеют различные свойства:

1)      универсальность;

2)      простота организации вычислительного процесса и контроля над точностью;

)        скорость сходимости.

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

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

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

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

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

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

1.      Формалев В.Ф., Ревизников Д.Л. Численные методы. -М.:ФИЗМАТЛИТ, 2004 - 400с.

.        Пирумов У.Г. Численные методы Учебное пособие - М Издательство МАИ, 1998 - 188с. с ил.

.        Кацман Ю.Я. Прикладная математика. Численные методы. Учебное пособие. - Томск: Изд. ТПУ, 2000. - 68 с.