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

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

В настоящей курсовой работе условие задачи дано в математической формулировке, поэтому необходимость в выполнении этапов 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 и х1 по формулам:

(1)

(2)

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

(3)

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

Таким путём получают две последовательности точек а1, а2, а3, …, an, … и x1, x2, x3, …, xn, …, приближаются с разных сторон к искомому корню. Преимущество описанного метода состоит в том, что при нём получаются приближённые значения как с избытком так и с достатком.

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

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

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

1),

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

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

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

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

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

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

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

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

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

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

,

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

.

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

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

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

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

и.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

f'(x)=(0,1x2 — 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. Выберем значение x0 для метода касательных. Т.к. f''(x)>0 и f (1)> 0, то x0=1.

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

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

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

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

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

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

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

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

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

f'(x)=(0,1x2 — 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. Выберем значение x0 для метода касательных. Т.к. f''(x)>0 и f (1)> 0, то x0=1.

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

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

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

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

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

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

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

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

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

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

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

13. f'(x11)= 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, то для метода касательных x21=1,1159

21. Вычислим производную: f'(x21)= 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 Тестовый пример

В качестве тестового примера рассмотрим линейное уравнение x3 — 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 с.

ПоказатьСвернуть
Заполнить форму текущей работой