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

Федеральное агентство по образованию ФГОУ СПО «Уфимский авиационный техникум»

Курсовая работа Нахождение корня уравнения методом касательных и комбинированным методом По дисциплине «Численные методы»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

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

(3)

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

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

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

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

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

1),

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

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

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

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

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

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

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

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

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

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

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

.

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

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

Если условие не выполняется, то нужно продолжить применение метода по схеме 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. Графическое отделение корней

2.2 Решение задачи методом касательных

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

f (a)=f (1)=0,1*1² -1*ln (1)=0,1>0,

f (b)=f (2)= 0,1*2² -2*ln (2)= -0,98 629<0

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

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

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, т. е. сохраняют знак, следовательно, условие выполняется.

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

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

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

Так что 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,

f (b)=f (2)= 0,1*2² -2*ln (2)= -0,98 629<0

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

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

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, т. е. сохраняют знак, следовательно, условие выполняется.

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

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

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

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

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

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

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

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

f (1,125) = -0,5 943 415,

f (2,0356) = -1,32 518 641

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

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

13. f'(x₁₁)= f'(1,125)=-0,65 722

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

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

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

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

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

f (1,1159)=0,2 152 287,

f (1,1302)=-0,10 595 182

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

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

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

22. Вычислим:

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

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

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

Ответ:

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

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

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

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

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

type

TForm1 = class (TForm)

Button1: TButton;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Edit1: TEdit;

Label4: TLabel;

Label5: TLabel;

Edit2: TEdit;

Label6: TLabel;

Edit3: TEdit;

Edit4: TEdit;

procedure Button1Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

Implementation

{$R *.dfm}

procedure TForm1. Button1Click (Sender: TObject);

function f (x:real):real;{Исходная функция}

begin

f:=0.1*sqr (x)-x*ln (x);

end;

function f1(x:real):real;{Первая производная функции}

begin

f1:=0.2*x-1+ln (x);

end;

function f2(x:real):real;{Вторая производная функции}

begin

f2:=0.2+1/x;

end;

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

begin

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

b:= strtofloat (edit2.Text);

eps:=strtofloat (edit3.Text);

if f (a)*f2(a)>=0 then x:=a else x:=b; {Выбор начального приближения}

repeat

t:=f (x)/f1(x);

x:=x-t;

until abs (t)<=eps;

edit4.text:= 'Ответ: корень = '+floattostrf (x, fffixed, 10,6); {Преобразует значение с плавающей запятой в строку}

end;

end.

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

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

type

TForm1 = class (TForm)

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Edit1: TEdit;

Edit2: TEdit;

Button1: TButton;

Edit3: TEdit;

Label6: TLabel;

Edit4: TEdit;

procedure Button1Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1. Button1Click (Sender: TObject);

function f (x:real):real;{Исходная функция}

begin

f:=0.1*sqr (x)-x*ln (x);

end;

function f1(x:real):real;{Первая производная функции}

begin

f1:=0.2*x-1+ln (x);

end;

function f2(x:real):real;{Вторая производная функции}

begin

f2:=0.2+1/x;

end;

var a, b, e, e1, x0,x11,x12:real;

begin

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

b:= strtofloat (edit2.Text);

e:=strtofloat (edit3.Text);

if f (a)*f2(a)>=0 then x0:=a else x0:=b; {Выбор начального приближения}

begin

x11:=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

a:=x11;

b:=x12;

x11:=a-f (a)/f1(a);

x12:=a-((b-a)*f (a)/(f (b)-f (a)));

e1:=(x11+x12)/2;

end;

edit4.text:='Ioaao: ei? aiu = '+floattostrf (x11,fffixed, 10,6); {Преобразует значение с плавающей запятой в строку}

end;

end;

end.

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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