Нахождение корней нелинейного уравнения

Курсовая

Информатика, кибернетика и программирование

Блок-схемы реализующие численные методы -для метода дихотомии: Блок-схема для метода хорд: Блок-схема для метода Ньютона: Листинг программы unit Unit1; interfce uses Windows Messges SysUtils Vrints Clsses Grphics Controls Forms Dilogs TeEngine Series ExtCtrls TeeProcs Chrt Menus OleCtnrs StdCtrls xCtrls OleCtrls VCF1 Mth; type TForm1 = clssTForm GroupBox1: TGroupBox; OleContiner2: TOleContiner; MinMenu1: TMinMenu; N1: TMenuItem; Chrt1: TChrt; Series1:...

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ НЕФТИ И ГАЗА им. И.М. ГУБКИНА

Кафедра информатики

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

по дисциплине «Информатика».

Тема: « Нахождение корней нелинейного уравнения»

Выполнил: студентка

Манепова А. М

группы: ГИ-12-05

Проверил:

Москва, 2013

Задание на выполнение курсовой работы. Теория нахождения корней нелинейного уравнения. Описание используемых численных методов. 1. Метод половинного деления (дихотомии) 2.Метод хорд 3. Метод Ньютона Расчеты в математическом пакете Mat lab Отчет о результатах вычисления приближенного значения корня уравнения в MS Excel. Результаты расчета с использованием Побора Параметра Результаты расчета с использованием Поиска Решений Описание приложения созданного в среде Delphi. Блок – схемы реализующие численные методы Листинг программы Изображение окна приложения Анализ полученных результатов Литература.

Задание на выполнение курсовой работы.

1. расчет , выполненный в математическом пакете Matlab (Mathematica 5 .) (файл-функция для описания нелинейного уравнения, график, решение в символьном и численном виде).
2. Нахождение корней нелинейного уравнения в электронных таблицах MS Excel (вид нелинейного уравнения, график нахождения корней нелинейного уравнения, найти корень нелинейного уравнения, используя средства условного анализа: «Побор параметра», «Поиск решения»).
3. Создание приложения для нахождения корней нелинейного уравнения в среде Delphi (вид нелинейного уравнения, график на заданном интервале, для каждого метода: результаты табулирования функции на заданном интервале с заданным шагом, для каждого метода численного метода пользовательскую подпрограмму с передачей параметров). Результаты отобразить на форме в виде таблицы и в файле. Предусмотреть изменение точности значения (Е <= 0 , 001).
4. вид уравнения

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

Пусть задана функция , непрерывная вместе со своими несколькими производными. Требуется найти все или некоторые вещественные корни уравнения

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

Рассмотрим три метода: 1) метод дихотомии (или деление отрезка пополам); 2) метод простой итерации и 3) метод Ньютона .

1. Метод половинного деления (дихотомии)

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

2.Метод хорд

При решении нелинейного уравнения методом хорд задаются интервалы , на котором существует только одно решение, и точность Ɛ. Затем через две точки с координатами (a,F(a)) и (b,F(b)) проводим отрезок прямой линии (хорду) и определяем точку пересечения этой линии с осью абцисс. Ели при этом F(a)*F(b) <0, то праву границу интервала пееносиим в точку x (b=x). Если указанное условие не выполняется, то в точку x переносится левая граница интервала (a=x). Поиск решения пекращается при достижении заданной точности |F(x)|>Ɛ. Вычисления ведутся до тех пор, пока не выполнится неравенство: . Итерационная формула метода хорд имеет вид:

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

Чтобы численно решить уравнение методом простой итерации , его необходимо привести к следующей форме: , где — сжимающее отображение .

Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Решение данного уравнения ищут в виде , тогда:

В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна , окончательная формула для такова:

С учётом этого функция определяется выражением:

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

Расчеты в математическом пакете Mat lab

В математическом пакете по условию задания был построен график функции и найден корень уравнения с использование символьного решения(solve ) и в численном виде используя встроенные функции: fzero и fsolve . Для описания моей функции использовала файл-функцию.

На следующем рисунке представлен графи функции:

Для записи команд использовала M -файл:

В командном окне были получены следующие результаты:

r 1 =

r 2 =

r 3 =

r 4 =

8.0000

r5 =

7.9979 -8.0000

Отчет о результатах вычисления приближенного значения корня уравнения в MS Excel.

MS Excel был проведен расчет приближенного значения корня уравнения с помощью встроенных возможностей «Подбор параметров» и «Поиск решений». Для выбора начального приближения предварительно мной была построена диаграмма.

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

x =-9 (исходя из диаграммы)

В результате использования Подбора Параметра был найден корень x =-8,01.

Результаты расчета с использованием Поиска Решений

В качестве начального приближения был выбран x =-9 (исходя из диаграммы)

После выполнения был получен следующий результат:

Поиск решения дал мне значение x = -8,00002

Описание приложения созданного в среде Delphi.

При создании приложения в среде Delphi в интерфейсе был предусмотрен вывод вида функции и графика. Нахождение корня нелинейного уравнения было реализовано с использование трех методов: Метод дихотомии, Метод Хорд и Метод Ньютона. В отличии от расчета в Excel , где корни находились с помощью подбора параметров и поиска решения, в программе предусмотрен ввод точности вычисления пользователем. Результаты расчета выводятся как в окно приложения так и в текстовый файл.

Блок – схемы реализующие численные методы

Блок-схема для метода дихотомии:

Блок-схема для метода хорд:

Блок-схема для метода Ньютона:

Листинг программы

unit Unit1;

interface

uses

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

Dialogs, TeEngine, Series, ExtCtrls, TeeProcs, Chart, Menus, OleCtnrs,

StdCtrls, AxCtrls, OleCtrls, VCF1, Math;

type

TForm1 = class(TForm)

GroupBox1: TGroupBox;

OleContainer2: TOleContainer;

MainMenu1: TMainMenu;

N1: TMenuItem;

Chart1: TChart;

Series1: TPointSeries;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

Label1: TLabel;

Edit1: TEdit;

GroupBox2: TGroupBox;

GroupBox3: TGroupBox;

GroupBox4: TGroupBox;

Label2: TLabel;

Label3: TLabel;

Edit2: TEdit;

Edit3: TEdit;

Edit4: TEdit;

Label4: TLabel;

Edit5: TEdit;

Label5: TLabel;

Edit7: TEdit;

Label7: TLabel;

F1Book1: TF1Book;

F1Book2: TF1Book;

F1Book3: TF1Book;

F1Book4: TF1Book;

Procedure N1Click(Sender: TObject);

Procedure N3Click(Sender: TObject);

Procedure FormCreate(Sender: TObject);

Procedure N4Click(Sender: TObject);

Procedure N5Click(Sender: TObject);

Private

{ Private declarations }

Public

{ Public declarations }

End;

const

xmin:real=-20;

xmax:real=20;

Form1: TForm1;

X,y,t,a,b,cor:real;

I,n:integer;

Fail:textfile;

implementation

{$R *.dfm}

function f(x:real):real;

begin

f:=(8+x)/(x*sqrt(sqr(x)-4));

end;

function f1(x:real):real;

begin

f1:=(-power(x,3)-16*x*x+32)/(x*X*sqrt(power(x*x-4,3)));

end;

procedure metoddix(ta,tb,eps:real;var xk:real;var kolvo: integer);

begin

kolvo:=0;

repeat

xk:=(ta+tb)/2;

kolvo:=kolvo+1;

Form1.F1book1.NumberRC:=xk;

Form1.F1book1.NumberRC:=f(xk);

if f(ta)*f(xk)<0 then tb:=xk

else ta:=xk;

until (abs(f(xk))<=eps);

end;

procedure metodhord(ta,tb,eps:real;var xk:real;var kolvo: integer);

begin

kolvo:=0;

repeat

xk:= ta-f(ta)*(ta-tb)/(f(ta)-f(tb));

kolvo:=kolvo+1;

Form1.F1book2.NumberRC:=xk;

Form1.F1book2.NumberRC:=f(xk);

if f(ta)*f(xk)<0 then tb:=xk

else ta:=xk;

until (abs(f(xk))<=eps);

end;

procedure metodnyutona(ta,eps:real;var xk:real;var kolvo: integer);

begin

kolvo:=0;

repeat

xk:= ta-f(ta)/f1(ta);

ta:=xk;

kolvo:=kolvo+1;

Form1.F1book3.NumberRC:=xk;

Form1.F1book3.NumberRC:=f(xk);

until (abs(f(xk))<=eps);

end;

procedure TForm1.N1Click(Sender: TObject);

begin

x:=xmin;

i:=0;

while x<=xmax do

begin

if abs(x)>5 then

Begin

I:=i+1;

Y:=f(x);

Series1.Addxy(x,y);

F1book4.NumberRC:=x;

F1book4.NumberRC:=y;

End;

x:=x+0.5;

end;

end;

procedure TForm1.N3Click(Sender: TObject); // Вычисление корня методом половинного деления

begin

F1book1.ClearRange(1,1,100,2,3);

t:=strtofloat(Edit1.Text);

a:=strtofloat(Edit2.Text);

b:=strtofloat(Edit3.Text);

metoddix(a,b,t,cor,n);

F1book4.TextRC:=" дихотомия ";

F1book4.TextRC:=" корень =";

F1book4.NumberRC:=cor;

F1book4.TextRC:="y=";

F1book4.NumberRC:=f(cor);

F1book4.TextRC:=" количество итераций =";

F1book4.NumberRC:=n;

Append(fail);

Writeln(fail);

Writeln(fail," Расчет методом дихотомии ");

closefile(fail);

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Assignfile(fail," отчет .txt");

Rewrite(fail);

Closefile(fail);

end;

procedure TForm1.N4Click(Sender: TObject); // Вычисление корня методом хорд

begin

F1book2.ClearRange(1,1,100,2,3);

t:=strtofloat(Edit1.Text);

a:=strtofloat(Edit5.Text);

b:=strtofloat(Edit4.Text);

metodhord(a,b,t,cor,n);

F1book4.TextRC:=" хорды ";

F1book4.TextRC:=" корень =";

F1book4.NumberRC:=cor;

F1book4.TextRC:="y=";

F1book4.NumberRC:=f(cor);

F1book4.TextRC:=" количество итераций =";

F1book4.NumberRC:=n;

Assignfile(fail," отчет .txt");

Append(fail);

Writeln(fail);

Writeln(fail," Расчет методом хорд ");

writeln(fail,"Точность расчета = ",t:10:7);

Writeln(fail,"Начальное приближение:a = ",a:8:3," b = ",b:8:3);

writeln(fail, " Найден корень : x = ",cor:8:3, " y=f(x)= ",f(cor):8:6);

writeln(fail, "Количество итераций = ",n);

closefile(fail);

end;

procedure TForm1.N5Click(Sender: TObject); // Вычисление корня методом Ньютона

begin

F1book3.ClearRange(1,1,100,2,3);

t:=strtofloat(Edit1.Text);

a:=strtofloat(Edit7.Text);

metodnyutona(a,t,cor,n);

F1book4.TextRC:=" Ньютона ";

F1book4.TextRC:=" корень =";

F1book4.NumberRC:=cor;

F1book4.TextRC:="y=";

F1book4.NumberRC:=f(cor);

F1book4.TextRC:=" количество итераций =";

F1book4.NumberRC:=n;

Assignfile(fail," отчет .txt");

Append(fail);

Writeln(fail);

Writeln(fail," Расчет методом Ньютона ");

writeln(fail,"Точность расчета = ",t:10:7);

Writeln(fail,"Начальное приближение:a = ",a:8:3," b = ",b:8:3);

writeln(fail, " Найден корень : x = ",cor:8:3, " y=f(x)= ",f(cor):8:6);

writeln(fail, "Количество итераций = ",n);

Closefile(fail);

end;

end.

Изображение окна приложения

Первоначальный интерфейс имеет следующий вид:

После выполнения расчетов при E <= 0,001:

В качестве отчета был сформирован файл «Отчет. txt .»:

Анализ полученных результатов

В соответствии с заданием на курсовую работу в математическом пакете мною был найден корень нелинейного уравнения (x =-8) и построен график.

В электронных таблицах был найден корень уравнения с помощью двух встроенных возможностей «Подбор параметра» и «Поиск решения» , при этом «Поиск решения» все же дал более точное значение. Результаты практически совпали с результатами в Matlab .

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

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

Литература.

1. Амосов А.А. и др. вычислительные методы для инженеров М., Высшая школа, 1994.
2. Фаронов В.В. Delphi. Программирование на зыке высокого уровня

3 . Уокенбах Д . Microsoft Office Excel 2007. Библия пользователя

Волков В.Б. Понятный самоучитель Excel 2010

Математика как наука возникла в связи с необходимостью решения практических задач: измерений на местности, навигации и т.д. Вследствие этого математика была численной математикой и ее целью было получение решения в виде числа. Численное решение прикладных задач всегда интересовало математиков. Крупнейшие представители прошлого сочетали в своих исследованиях изучение явлений природы, получение их математического описания, т.е. его математической модели и его исследование. Анализ усложненных моделей потребовал создания специальных, обычно численных методов решения задач. Названия некоторых таких методов свидетельствуют о том, что их разработкой занимались крупнейшие ученые своего времени. Это методы Ньютона, Эйлера, Лобачевского, Гаусса, Чебышева, Эрмита.

Настоящее время характерно резким расширением приложений математики, во многом связанным с созданием и развитием средств вычислительной техники. В результате появления ЭВМ менее чем за 40 лет скорость выполнения операций возросла от 0,1 операции в секунду при ручном счете до 10 операций в секунду на современных ЭВМ.

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

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

во-первых, только применение математических методов позволяет придать количественный характер исследованию того или иного явления материального мира;

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

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

Математические модели.

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

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

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

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

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

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

Рассмотрим задачу нахождения корней нелинейного уравнения

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

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

Существование на найденном отрезке , по крайней мере, одного корня уравнения (1) следует из условия Больцано:

f(a)*f(b)<0 (2)

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

При локализации корней важно так же знание основных свойств данного типа уравнения. К примеру, напомним, некоторые свойства алгебраических уравнений:

где вещественные коэффициенты.

• а) Уравнение степени n имеет n корней, среди которых могут быть как вещественные, так и комплексные. Комплексные корни образуют комплексно-сопряженные пары и, следовательно, уравнение имеет четное число таких корней. При нечетном значении n имеется, по меньшей мере, один вещественный корень.
• б) Число положительных вещественных корней меньше или равно числа переменных знаков в последовательности коэффициентов. Замена х на -х в уравнении (3) позволяет таким же способом оценить число отрицательных корней.

На втором этапе решения уравнения (1), используя полученное начальное приближение, строится итерационный процесс, позволяющий уточнять значение корня с некоторой, наперед заданной точностью. Итерационный процесс состоит в последовательном уточнении начального приближения. Каждый такой шаг называется итерацией. В результате процесса итерации находится последовательность приближенных значений корней уравнения. Если эта последовательность с ростом n приближается к истинному значению корня x , то итерационный процесс сходится. Говорят, что итерационный процесс сходится, по меньшей мере, с порядком m, если выполнено условие:

где С>0 некоторая константа. Если m=1 , то говорят о сходимости первого порядка; m=2 - о квадратичной, m=3 - о кубической сходимостях.

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

или малости невязки:

Эта работа посвящена изучению алгоритма решения нелинейных уравнений с помощью метода Ньютона.

Существует много различных методов решения нелинейных уравнений, некоторые из них представлены ниже:

• 1)Метод итераций . При решении нелинейного уравнения методом итераций воспользуемся записью уравнения в виде x=f(x). Задаются начальное значение аргумента x 0 и точность е. Первое приближение решения x 1 находим из выражения x 1 =f(x 0), второе - x 2 =f(x 1) и т.д. В общем случае i+1 приближение найдем по формуле xi+1 =f(xi). Указанную процедуру повторяем пока |f(xi)|>е. Условие сходимости метода итераций |f"(x)|
• 2)Метод Ньютона . При решении нелинейного уравнения методом Ньтона задаются начальное значение аргумента x 0 и точность е. Затем в точке(x 0 ,F(x 0)) проводим касательную к графику F(x) и определяем точку пересечения касательной с осью абсцисс x 1 . В точке (x 1 ,F(x 1)) снова строим касательную, находим следующее приближение искомого решения x 2 и т.д. Указанную процедуру повторяем пока |F(xi)| > е. Для определения точки пересечения (i+1) касательной с осью абсцисс воспользуемся следующей формулой

x i+1 =x i -F(x i) F"(x i).

Условие сходимости метода касательных F(x 0) F""(x)>0, и др.

3). Метод дихотомии. Методика решения сводится к постепенному делению начального интервала неопределённости пополам по формуле

С к =а к +в к /2.

Для того чтобы выбрать из двух получившихся отрезков необходимый, надо находить значение функции на концах получившихся отрезков и рассматривать тот на котором функция будет менять свой знак, то есть должно выполняться условие f (а к)* f (в к)<0.

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

4). Метод хорд . Идея метода состоит в том, что на отрезке строится хорда стягивающая концы дуги графика функции y=f(x), а точка c, пересечения хорды с осью абсцисс, считается приближенным значением корня

c = a - (f(a)Ч (a-b)) / (f(a) - f(b)),

c = b - (f(b)Ч (a-b)) / (f(a) - f(b)).

Следующее приближение ищется на интервале или в зависимости от знаков значений функции в точках a,b,c

x* О , если f(с)Ч f(а) > 0 ;

x* О , если f(c)Ч f(b) < 0 .

Если f"(x) не меняет знак на , то обозначая c=x 1 и считая начальным приближением a или b получим итерационные формулы метода хорд с закрепленной правой или левой точкой.

x 0 =a, x i+1 = x i - f(x i)(b-x i) / (f(b)-f(x i), при f "(x)Ч f "(x) > 0 ;

x 0 =b, x i+1 = x i - f(x i)(x i -a) / (f(x i)-f(a), при f "(x)Ч f "(x) < 0 .

Сходимость метода хорд линейная

Алгебраические и трансцендентные уравнения. Методы локализации корней.

Наиболее общий вид нелинейного уравнения:

f(x) =0 (2.1)

где функция f(x) определена и непрерывна на конечном или бесконечном интервале [а, b].

Определение 2.1. Всякое число, обращающее функцию f(x) в нуль, называется корнем уравнения (2.1).

Определение 2.2. Число, называется корнем k-ой кратности, если при вместе с функцией f(x) равны нулю ее производные до (к-1)-го порядка включительно:

Определение 2.3. Однократный корень называется простым.

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

Определение 2.4 . Уравнение (2.1) называется алгебраическим, если функция F(x) является алгебраической.

Путем алгебраических преобразований из всякого алгебраического уравнения можно получить уравнение в канонической форме:

где -- действительные коэффициенты уравнения, х -- неизвестное.

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

Определение 2.5. Уравнение (2.1) называется трансцендентным, если функция F(x) не является алгебраической.

Решить уравнение (2.1) означает:

• 1. Установить имеет ли уравнение корни.
• 2. Определить число корней уравнения.
• 3. Найти значения корней уравнения с заданной точностью.

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

Алгоритм нахождения корня уравнения с помощью численного метода состоит из двух этапов:

• 1) отделение или локализация корня, т.е. установление промежутка , в котором содержится один корень:
• 2) уточнение значения корня методом последовательных приближений.

Методы локализации корней. Теоретической основой алгоритма отделения корней служит теорема Коши о промежуточных значениях непрерывной функции.

Теорема 2.1. Если функция у = f(х) непрерывна на отрезке [а,b] и f(а)=А, f(b)=В, то для любой точки С, лежащей между А и В, существует точка, что.

Следствие. Если функция у = f(х) непрерывна на отрезке [а,b ] и на его концах принимает значения разных знаков, то на этом отрезке существует хотя бы один корень уравнения f(х) = 0.

Пусть область определения и непрерывности функции является конечным отрезком [а,b] . Разделим отрезок на n частей: ,

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

т.е. , или, . Эти отрезки и содержит хотя бы по одному корню.

Теорема 2.2. Если функция у = f(х) непрерывна на отрезке [а;b ], f(а)f(b)<0 и f`(х) на интервале (а;b) сохраняет знак, то внутри отрезка [а;b] существует единственный корень уравнения f(х) = 0.

Для отделения корней можно использовать также график функции у = f(х). Корнями уравнения (2.1) являются те значения х, при которых график функции y=f(х) пересекает ось абсцисс. Построение графика функции даже с малой точностью обычно дает представление о расположении корней уравнения (2.1). Если построение графика функции у=f(x) вызывает затруднение, то исходное уравнение (2.1) следует преобразовать к виду ц1(х) = ц2(х) таким образом, чтобы графики функций у = ц1(х) и у = ц2(х) были достаточно просты. Абсциссы точек пересечения этих графиков и будут корнями уравнения (2.1).

Пример 1. Отделить корни уравнения x 2 -2cosx=0.

Решение. Рассмотрим два способа отделения корней.

• а) Графический способ. Перепишем уравнение в виде x 2 =2cosx и построим график функций y=x 2 и y=2cosx в одной и той же системе координат (рисунок 5). так как эти графики пересекаются в двух точках, уравнение имеет два корня, расположенные симметрично относительно начала координат на интервалах (-/2; 0) и (0; /2).
• б) Аналитический способ. Пусть f(x)= x 2 -2cosx. Так как f(x) четная функция, то достаточно рассмотреть только неотрицательные значения x. В силу неравенства 2cosx2

Производная f"(x) =2(x+sinx). На интервале (0; /2) f"(x) >0 , следовательно, f(x) здесь монотонно возрастает и ее график может пересечь ось х не более, чем в одной точке. Заметим, что f(0)=- 2<0, а f(/2)=(/2) 2 >0. Значит, уравнение имеет один положительный корень, лежащий на интервале (0; /2). В силу четности функции уравнение имеет также один отрицательный корень, симметричный положительному. Теперь перейдем к уточнению корня. Для применения комбинированного метода уточнения корня необходимо убедится, что f ""(x) на (0; /2) сохраняет знак, и выбрать начальное приближение корня для применения метода касательных. Оно должно удовлетворять условию: f(x)f ""(x) >0. Так как f ""(x) =2(1+cosx) положительна на , то за начальное приближение корня в методе касательных может быть взято /2. Следовательно, можно положить x =/21,570796, x 1 =0 (см схему алгоритма). В нашем случае метод хорд будет давать приближенное значение корня с недостатком, а метод касательных - с избытком.

Рассмотрим один итерационный шаг уточнения корня. Вычислим значения f(0), f(/2), f"(/2). Новые значения x 1 и x найдем соответственно по формулам:

|x-x 1 |=0,387680,4>10 -4 =.

Заданная точность не достигнута, и вычисления нужно продолжить.

Номер итерации	x 1		f(x 1 )			|x- x 1 |

Следовательно, приближенное значение корня с нужной точностью найдено в результате трех итераций и приближенно равно 1,0217.

В силу симметрии графика функции f(x) значение второго корня приближенно равно -1,0217.

Уточнение корня.

Постановка задачи . Допустим, что искомый корень уравнения (2.1) отделен, т.е. найден отрезок [а; b], на котором имеется один и только один корень уравнения. Любую точку этого отрезка можно принять за приближенное значение корня. Погрешность такого приближения не превосходит длины [а; b]. Следовательно, задача отыскания приближенного значения корня с заданной точностью сводится к нахождению отрезка [а; b] (b- a <), содержащего только один корень уравнения (2.1). Эту задачу обычно называют задачей уточнения корня.

Описание численных методов. Численные методы позволяют найти решения определенных задач, заранее зная, что полученные результаты будут вычислены с определенной погрешностью, поэтому для многих численных методов необходимо заранее знать «уровень точности», которому будет соответствовать полученное решение.

В этой связи задача нахождения корней многочлена вида (3.1)

представляет особый интерес, т.к. формулы нахождения корней даже кубического уравнения достаточно сложны. Если необходимо отыскать корни многочлена, степень которого равна, например, 5 - то без помощи численных методов не обойтись, тем более, что вероятность наличия у такого многочлена натуральных (или целых, или точных корней с «короткой» дробной частью) довольно мала, а формул для нахождения корней уравнения степени, превышающей 4, не существует. Де-факто все дальнейшие операции будут сводиться лишь к уточнению корней , интервалы которых приблизительно известны заранее. Проще всего эти «приблизительные» корни находить, используя графические методы.

Для нахождения корней многочлена существует несколько численных методов: метод итераций, метод хорд и касательных, метод половинного деления, метод секущих.

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

Суть метода половинного деления заключается в следующем:

• - дана функция F(x);
• - определена допустимая погрешность Q;
• - определен некоторый интервал [ a , b ], точно содержащий решение уравнения.

1) Вычисляем значение координаты Е, беря середину отрезка , т.е.

Е= (a + b) / 2 (3.2)

• 2) Вычисляем значения F(a), F(b), F(E), и осуществляем следующую проверку: Если F(E)>Q, то корень с указанной точностью найден. Если F(E)
• 3) Переходим к пункту 1.

Метод простых итераций (метод последовательных приближений). Заменим уравнение (2.1) эквивалентным ему уравнением

x=(x) (3.3)

можно сделать различными способами, например

х=х+сf(x), c0. (3.4)

Предположим, что выбрано некоторое начальное приближение корня уравнения (3.3). Определим числовую последовательность по формулам

х n+1 =(x n ), n=0,1,2,… (3.5)

Такую последовательность называют итерационной.

Если на отрезке , содержащем х 0 и все последующие приближения х n , nN, функция (x) имеет непрерывную производную "(x) и |"(x)|q<1, то итерационная последовательность (3.5) сходится к единственному на корню уравнения (3.3). Скорость сходимости определяется неравенством

Из этого неравенства, в частности, следует, что скорость сходимости метода простой итерации зависит от величины q: чем меньше q, тем быстрее сходимость.

Следовательно, на практике при нахождении корней методом простой итерации желательно представить уравнение (2.1) в форме (3.3) таким образом, чтобы производная "(x) в окрестности корня по абсолютной величине была, возможно, меньше. Для этого иногда пользуются параметром с из формулы (3.4).

Метод Ньютона (метод касательных). Если известно достаточно хорошее начальное приближение, для которого выполняется неравенство:

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

В качестве начального приближения можно использовать границы интервала, причем:

Если на.

На каждой итерации, данного метода, объем вычислений больше чем в методах биссекций и итераций, поскольку приходится находить не только значение функции, но и ее производной. Однако скорость сходимости метода Ньютона значительно выше.

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

где - наибольшее значение модуля второй производной на отрезке, - наименьшее значение модуля первой производной на отрезке.

Правило останова:

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

Надо отметить, что существуют также отдельно метод хорд (дает значение корня с недостатком) и метод касательных (с избытком). Однако преимущество комбинированного метода заключается в «двустороннем сжатии» рассматриваемого отрезка.

Рассмотрим следующий случай:

• - дана функция F(x) и построен ее график;
• - определена допустимая погрешность Q
• - на основании графика определен отрезок , на котором график функции пересекает ось абсцисс, следовательно, на этом отрезке существует корень рассматриваемого многочлена (обозначим его через A)

Дальнейший алгоритм сводится к следующим действиям:

• 1) строим касательную к графику функции в точке F(b)
• 2) вычисляем координату х пересечения касательной с осью абсцисс по формуле (3.9) и обозначаем ее через b"
• 3) строим к графику функции хорду, проходящую через точки F(a) и F(b).
• 4) Вычисляем точку пересечения хорды с осью абсцисс по формуле (2) и обозначаем ее через a".

Таким образом мы получаем новый отрезок , который (по определениям хорды и касательной) по прежнему содержит решение уравнения A.

Теперь принимаем отрезок за новый отрезок и повторяем шаги 1-4 до тех пор, пока разность F(b)-F(a) не станет меньше первоначально заложенной погрешности Q. Отметим также, что после этого рекомендуется в качестве искомого решения взять среднее арифметическое F(a) и F(b).

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

Замечание к методу хорд и касательных. Так как для решения поставленной задачи требуется отыскание производной функции F(x), метод хорд и касательных достаточно трудно реализуем на программном уровне, т.к. правила вычисления производных в общем виде довольно громоздки для «понимания» ЭВМ; при непосредственном указании производной для каждой степени многочлена память компьютера серьезно загружается, что очень замедляет работу, а задание функции и, соответственно, ее производной непосредственно в программном коде - недопустимо. Однако, используя данный метод, сходимость интервала к корню происходит наиболее быстро, особенно если совместить метод хорд и касательных с методом бисекции, т.к. середина нового отрезка зачастую дает вполне удовлетворительное решение.

Метод секущих. Метод секущих может быть получен из метода Ньютона при замене производной приближенным выражением - разностной формулой:

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

Алгоритм метода секущих:

1) заданы начальное значение и погрешность. Вычислим

2) для n = 1,2, ….. пока выполняется условие, вычисляем по формуле (3.8).

Уравнение типа F(x)=0 или x=f(x) называется нелинейным. Решить уравнение это значит найти такое x, при котором уравнение превращается в тождество. В общем случае уравнение может иметь 0; 1; 2; ...∞ корней. Рассмотренные ниже численные методы решения нелинейных уравнений позволяют находить один корень на заданном интервале . При этом на интервале должен существовать только один корень. Рассмотрим несколько методов решения нелинейных уравнений .

1. Метод перебора . При решении нелинейного уравнения методом перебора задаются начальное значение аргумента x=a и шаг h, который при этом определяет и точность нахождения корней нелинейного уравнения. Пока выполняется условие F(x)*F(x+h)>0 аргумент x увеличиваем на шаг h (x=x+h). Если произведение F(x)*F(x+h) становится отрицательным, то на интервале существует решение уравнения. Структограмма метода приведена на рисунке.

   
   

2. Метод половинного деления . При решении нелинейного уравнения методом половинного деления задаются интервал , на котором существует только одно решение, и желаемая точность ε. Затем определяется середина интервала с=(а+b)/2 и проверяется условие F(a)∙F(c)<0. Если указанное условие выполняется, то правую границу интервала b переносим в среднюю точку с (b=c). Если условие не выполняется, то в среднюю точку переносим левую границу(a=c). Деление отрезка пополам продолжается пока |b-a|>ε. Структограмма решения нелинейных уравнений методом половинного деления приведена на рисунке.

   Пока |b-a|>ε
   F(a)∙F(c)<0

   
   

   Рис. Структограмма для метода половинного деления

3. Метод хорд . При решении нелинейного уравнения методом хорд задаются интервал , на котором существует только одно решение, и точность ε. Затем через две точки с координатами (a,F(a)) и (b,F(b)) проводим отрезок прямой линии (хорду) и определяем точку пересечения этой линии с осью абсцисс (точка c). Если при этом F(a)∙F(c)<0, то правую границу интервала переносим в точку с (b=c). Если указанное условие не выполняется, то в точку c переносится левая граница интервала (а=с). Поиск решения прекращается при достижении заданной точности |F(c)|< ε. Для определения точки пересечения хорды с осью абсцисс воспользуемся следующей формулой (попытайтесь получить формулу самостоятельно).Структограмма метода хорд показана на рисунке.

   Пока |F(c)|>ε
   F(a)∙F(c)<0

   
   

   Рис. Структограмма для метода хорд

4. Метод касательных . При решении нелинейного уравнения методом касательных задаются начальное значение аргумента x 0 и точность ε. Затем в точке(x 0 ,F(x 0)) проводим касательную к графику F(x) и определяем точку пересечения касательной с осью абсцисс x 1 . В точке (x 1 ,F(x 1)) снова строим касательную, находим следующее приближение искомого решения x 2 и т.д. Указанную процедуру повторяем пока |F(x i)| > ε. Для определения точки пересечения (i+1) касательной с осью абсцисс воспользуемся следующей формулой (получите формулу самостоятельно). Условие сходимости метода касательных F(x 0)∙F""(x 0)>0. Структограмма решения нелинейных уравнений методом касательных показана на рис.

   
   

5. Метод хорд-касательных . Если в методе касательных производную функции F"(x i) заменить отношением конечных приращений, то получаем расчетную формулу для метода хорд-касательных . Порядок выполнения вычислений в данном методе аналогичен рассмотренному ранее.
6. Метод итераций . При решении нелинейного уравнения методом итераций воспользуемся записью уравнения в виде x=f(x) . Задаются начальное значение аргумента x 0 и точность ε. Первое приближение решения x 1 находим из выражения x 1 =f(x 0), второе - x 2 =f(x 1) и т.д. В общем случае i+1 приближение найдем по формуле x i +1 =f(x i). Указанную процедуру повторяем пока |f(x i)|>ε. Условие сходимости метода итераций |f"(x)|<1. Структограмма метода итераций показана на рис.

   
   

Контрольное задание. Лабораторная работа 4.

Решение нелинейных уравнений.

Задание . Решить нелинейное уравнениеуказанными в табл. методами, предварительно определив интервал , на котором существует решение уравнения. Сделать проверку решения.

Варианты уравнений и методов их решения приведены в таблице.

Варианты уравнений и методов их решения

	Уравнение	Методы решения
		перебора и хорд
		Перебора и касательных
		Перебора и хорд-касательных
		Перебора и половинного деления
		перебора и хорд
		Перебора и касательных
		Перебора и хорд-касательных
		Перебора и половинного деления
		перебора и хорд
		Перебора и касательных
		Перебора и хорд-касательных
		Перебора и половинного деления
		перебора и хорд
		Перебора и касательных
		Перебора и хорд-касательных
		Перебора и половинного деления
		перебора и хорд
		Перебора и касательных
	x 2 =exp(-x 2)-1	Перебора и хорд-касательных
		Перебора и половинного деления
		перебора и хорд
		Перебора и касательных
		Перебора и хорд-касательных
		Перебора и половинного деления

1. Название, цель работы и задание.
2. Математическое описание, алгоритм (структограмма) и текст программы.
3. Результаты расчета, проверка и выводы по работе.

Рассмотрим задачу нахождения корней нелинейного уравнения

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

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

Существование на найденном отрезке , по крайней мере, одного корня уравнения (1) следует из условия Больцано:

f(a)*f(b)<0 (2)

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

При локализации корней важно так же знание основных свойств данного типа уравнения. К примеру, напомним, некоторые свойства алгебраических уравнений:

где вещественные коэффициенты.

• а) Уравнение степени n имеет n корней, среди которых могут быть как вещественные, так и комплексные. Комплексные корни образуют комплексно-сопряженные пары и, следовательно, уравнение имеет четное число таких корней. При нечетном значении n имеется, по меньшей мере, один вещественный корень.
• б) Число положительных вещественных корней меньше или равно числа переменных знаков в последовательности коэффициентов. Замена х на -х в уравнении (3) позволяет таким же способом оценить число отрицательных корней. итерация Ньютон дихотомия нелинейный

На втором этапе решения уравнения (1), используя полученное начальное приближение, строится итерационный процесс, позволяющий уточнять значение корня с некоторой, наперед заданной точностью. Итерационный процесс состоит в последовательном уточнении начального приближения. Каждый такой шаг называется итерацией. В результате процесса итерации находится последовательность приближенных значений корней уравнения. Если эта последовательность с ростом n приближается к истинному значению корня x , то итерационный процесс сходится. Говорят, что итерационный процесс сходится, по меньшей мере, с порядком m, если выполнено условие:

где С>0 некоторая константа. Если m=1 , то говорят о сходимости первого порядка; m=2 - о квадратичной, m=3 - о кубической сходимостях.

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

или малости невязки:

Эта работа посвящена изучению алгоритма решения нелинейных уравнений с помощью метода Ньютона.