Численные методы для нахождения корней нелинейного уравнения

Содержание: 1.Задание…2.Теоретическое обоснование методов решения задачи:….2.1 Метод половинного деления… 2.2 Метод Ньютона…2.3 Метод простых итераций…3.График исходной функции:…3.1 Общий график функции….3.2 График функции вблизи первого пол корня…3.3 Исходные данные для решения задачи…4. Блок-схема задачи…10 5.

Исходный текст программы… 6. Результаты расчетов…7. Графики сходимости…8. Выводы….1.Задание. Найти заданное пользователем количество корней уравнения , где (вариант №9) тремя методами: методом половинного деления, методом Ньютона, методом простых итераций. 2.Теоретическое обоснование методов решения задачи: Пусть рассматривается уравнение . Корнем уравнения называется значение , при котором .

Корень называется простым, если , в противном случае корень называется кратным. Целое число m называется кратностью корня , если для k=1,2,3 m-1 и . Постановка задачи: вычисления приближенного значения корня с точностью : найти такое значения , что . Решение задачи разбивается на два этапа: на первом этапе осуществляют локализацию корней, на втором этапе производят итерационное уточнение корней. На этапе локализации корней находят достаточно узкие

отрезки ( или отрезок, если корень единственный), которые содержат один и только один корень уравнения . На втором этапе вычисляют приближенное значение корня с заданной точностью. Часто вместо отрезка локализации достаточно указать начальное приближение к корню. 2.1 Метод половинного деления. Пусть [a,b] v отрезок локализации. Предположим, что функция f(x) непрерывна на [a,b] и на концах принимает значения разных знаков .

Алгоритм метода половинного деления состоит в построении последовательности вложенных отрезков, на концах которых функция принимает значения разных знаков. Каждый последующий отрезок получают делением пополам предыдущего. Опишем один шаг итераций метода. Пусть на k-ом шаге найден отрезок такой, что . Найдем середину отрезка . Если , то - корень и задача решена.

Если нет, то из двух половин отрезка выбираем ту, на концах которой функция имеет противоположные знаки: , , если , , если Критерий окончания итерационного процесса: если длина отрезка локализации меньше 2 , то итерации прекращают и в качестве значения корня с заданной точностью принимают середину отрезка. Теорема о сходимости метода половинного деления. Пусть функция f(x) непрерывна на [a,b] и на концах принимает значения разных знаков .Тогда метод сходится и справедлива оценка погрешности :

2.2 Метод Ньютона. Расчетная формула метода Ньютона имеет вид: . Геометрически метод Ньютона означает, что следующее приближение к корню есть точка пересечения с осью ОХ касательной, проведенной к графику функции y=f(x) в точке . Теорема о сходимости метода Ньютона. Пусть - простой корень уравнения , в некоторой окрестности которого функция дважды непрерывно дифференцируема. Тогда найдется такая малая - окрестность корня , что при

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

является малая окрестность корня . Неудачный выбор может дать расходящуюся итерационную последовательность. 2.3 Метод простых итераций. Для применения метода простой итерации следует исходное уравнение преобразовать к виду, удобному для итерации . Это преобразование можно выполнить различными способами. Функция называется итерационной функцией. Расчетная формула метода простой итерации имеет вид: . Теорема о сходимости метода простой итерации. Пусть в некоторой - окрестности корня функция дифференцируема

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

Если величина , то можно использовать более простой критерий окончания итераций: . Ключевой момент в применении метода простой итерации состоит в эквивалентном преобразовании уравнения. Способ, при котором выполнено условие сходимости метода простой итерации, состоит в следующем: исходное уравнение приводится к виду . Предположим дополнительно, что производная знакопостоянна и на отрезке [a,b]. Тогда при выборе итерационного параметра метод сходится и значение .

3.График исходной функции. 3.1 Общий график функции. График исходной функции построен в приложение Excel на интервале -10…10 с шагом 01. Данные для построения графика получены из файла data1.txt, который создается в результате работы программы dannie_d.pas 3.2 График функции вблизи первого пол корня. Из данного графика видно, что первый положительный корень лежит в интервале 1.5…1.7 3.3

Исходные данные для решения задачи. Подробный анализ графика функции позволил выявить следующие локализации корней: • Нечетные положительные корни: первый корень(1.5;1.7) третий корень(3.5;3.7) пятый корень(5.5; 5.7) и т.д. • Четные положительные корни: второй корень(2.4;2.8) четвертый корень (4.4;4.8) шестой корень(6.4;6.8) и т.д. • Нечетные отрицательные корни: первый корень(-0.7;-0.4) третий корень(-2.7;-2.4) пятый корень(-4.7;-4.4) и т.д. • Четные отрицательные корни: второй корень(-1.6;-1.3) четвертый корень (-3.6;-3.3) шестой корень(-5.6;-5.3)

и т.д В программе реализован механизм связи между данными интервалами, что позволило вычислять любое заданное число корней. В качестве точности вычисления взята величина e=0.00001. Локализация первого положительного и первого отрицательного корня, а также точность вычислений занесены в файл data2.txt, с которым работает программа. 4. Блок-схема задачи. Упрощенная блок-схема основной программы.

Упрощенная блок-схема процедуры delenie (метод половинного деления). Данная блок-схема отображает способ нахождения только одного корня уравнения, реальная же процедура delenie способна находить любое число корней. Упрощенная блок-схема процедуры niton (метод Ньютона). Данная блок-схема отображает способ нахождения только одного корня уравнения, реальная же процедура niton способна находить любое число корней.

Упрощенная блок-схема процедуры inter (метод простых итераций). Данная блок-схема отображает способ нахождения только одного корня уравнения, реальная же процедура inter способна находить любое число корней. Итерационная функция имеет вид x=x+f(x)*l(x)=g(x). Анализ производной итерационной функции g(x) позволил определить что функция l(x) должна принимать значения 1/10 и -1/10 в зависимости от того какой корень рассматривается - четный или нечетный, положительный

или отрицательный. 5. Исходный текст программы. program korni; uses crt,Windos; const pi=3.14159265358979323846; var a1,a2,b1,b2,a1v,a2v,b1v,b2v,e,c1,c2,c01, c02:single; code,vr,nid1,nin1,nii1,nid2,nin2,nii2,G1 ,G2,i,met,Nint:integer; met1,met2,met3,result:text; Yer,Mon,Day,dw,h,m,s,sc:word; procedure dann; var fl:text; s:string; begin assign(fl data2.txt'); reset(fl); while not eof(fl) do begin readln(fl,s); if pos('a1= s)>0 then begin delete(s,1,3); val(s,a1,code);

end; if pos('b1= s)>0 then begin delete(s,1,3); val(s,b1,code); end; if pos('a2= s)>0 then begin delete(s,1,3); val(s,a2,code); end; if pos('b2= s)>0 then begin delete(s,1,3); val(s,b2,code); end; if pos('e= s)>0 then begin delete(s,1,2); val(s,e,code); end; end; close(fl); end; procedure met1_nil; begin assign(met1 met1.txt'); rewrite(met1); close(met1); end; procedure met2_nil; begin assign(met2 met2.txt'); rewrite(met2); close(met2); end; procedure met3_nil; begin assign(met3 met3.txt'); rewrite(met3);

close(met3); end; function f(x:real):real; begin if x<>0 then f:=1/x-pi*cos(pi*x) else f:=10000; end; function znproizv1(x:single):single; begin znproizv1:=-1/(x*x)+(pi*pi)*sin(pi*x); end; procedure delenie; begin nid1:=0; nid2:=0; assign(met1 met1.txt'); append(met1); if met=1 then repeat c1:=(a1+b1)/2; writeln(met1,c1:4:10 f(c1):4:10); if f(a1)*f(c1)>0 then a1:=c1; if f(b1)*f(c1)>0 then b1:=c1; if f(c1)=0 then begin a1:=0; b1:=0 end; nid1:=nid1+1; until b1-a1<e; if met=2 then repeat c2:=(a2+b2)/2;

writeln(met1,c2:4:10 f(c2):4:10); if f(a2)*f(c2)>0 then a2:=c2; if f(b2)*f(c2)>0 then b2:=c2; if f(c2)=0 then begin a2:=0; b2:=0 end; nid2:=nid2+1; until abs(b2-a2)<e; close(met1); end; procedure niton; var cvs1,cvs2:single; begin nin1:=1; nin2:=1; assign(met2 met2.txt'); append(met2); {repeat c01a:=a1+i*e; c01b:=b1-i*e; i:=i+1; until ((f(c01a)*znproizv2(c01a))>0) or ((f(c01b)*znproizv2(c01b))>0);} {if (f(c01a)*znproizv2(c01a))>0 then c01:=c01a else} if met=1 then begin c01:=a1; writeln(met2,c01:4:10

f(c01):4:10); repeat c1:=c01-f(c01)/znproizv1(c01); writeln(met2,c1:4:10 f(c1):4:10); nin1:=nin1+1; cvs1:=c01; c01:=c1; until abs(c1-cvs1)<e; end; {i:=0; repeat c02a:=a2+i*e; c02b:=b2-i*e; i:=i+1; until ((f(c02a)*znproizv2(c02a))>0) or ((f(c02b)*znproizv2(c02b))>0); if (f(c02a)*znproizv2(c02a))>0 then c02:=c02a else} if met=2 then begin c02:=a2; writeln(met2,c02:4:10 f(c02):4:10); repeat c2:=c02-f(c02)/znproizv1(c02); writeln(met2,c2:4:10 f(c2):4:10); nin2:=nin2+1; cvs2:=c02; c02:=c2; until abs(c2-cvs2)<e; end; close(met2);

end; procedure inter; var cvs1,cvs2:single; begin assign(met3 met3.txt'); append(met3); nii1:=1; nii2:=1; if met=1 then begin c01:=a1; writeln(met3,c01:4:10 f(c01):4:10); repeat if nint=0 then c1:=c01+1/(10*c01)-pi*cos(pi*c01)/10 else c1:=c01-1/(10*c01)+pi*cos(pi*c01)/10; writeln(met3,c1:4:10 f(c1):4:10); cvs1:=c01; c01:=c1; nii1:=nii1+1; until abs(c1-cvs1)<e; end; if met=2 then begin c02:=a2; writeln(met3,c02:4:10 f(c02):4:10); repeat if nint=0 then c2:=c02+1/(10*c02)-pi*cos(pi*c02)/10 else c2:=c02-1/(10*c02)+pi*cos(pi*c02)/10;

writeln(met3,c2:4:10 f(c2):4:10); cvs2:=c02; c02:=c2; nii2:=nii2+1; until abs(c2-cvs2)<e; end; close(met3); end; {Main code} begin assign(result result.txt'); append(result); met:=0; clrscr; dann; a1v:=a1; b1v:=b1; a2v:=a2; b2v:=b2; writeln('Искомое уравнение f(x)=1/x-pi*cos(x*pi) имеет бесконечное число решений ); writeln(' поэтому введите количество корней которые надо найти:'); writeln; write('Введите количество положительных корней, которое надо найти '); readln(G1); writeln; write('Введите количество отрицательных

корней, которое надо найти '); readln(G2); clrscr; if (G1=0) and (G2=0) then begin writeln('Вы укозали, что корни искать не нужно. Программа завершается ); readln; exit; end; clrscr; writeln('Выберите способ решения задачи:'); writeln('1.Метод половинного деления'); writeln('2.Метод Ньютона’); writeln('3.Метод простых интеракций’); readln(vr); clrscr; case vr of 1:begin met1_nil; getdate(yer,mon,day,dw); gettime(h,m,s,sc); writeln(result '); writeln(result

Metod polovinnogo deleniy. Date: day mon yer h : m); writeln(result Option: Search: G1:3 polog. korney G2:3 otric. korney. eps: e:1:10); if G1<>0 then begin writeln('Положительные корни:'); writeln(result Polog. korni:'); for i:=1 to G1 do begin met:=1; delenie; if (i+1) mod 2=0 then begin a1v:=a1v+0.9; b1v:=b1v+1.1 end else begin a1v:=a1v+1.1; b1v:=b1v+0.9; end; writeln('X i = c1:4:8

F(X i )= f(c1):4:9); writeln(result X i = c1:4:8 F(X i )= f(c1):4:9 n interakciy= nid1); a1:=a1v; b1:=b1v; end; end else writeln('Вы указали что нет необходимости искать положительные корни'); if G2<>0 then begin writeln('Отрицательные корни'); writeln(result Otric. korni:'); for i:=1 to G2 do begin met:=2; delenie; if (i+1) mod 2=0 then begin a2v:=a2v-0.9; b2v:=b2v-0.9; end else begin a2v:=a2v-1.1; b2v:=b2v-1.1; end; writeln('X i = c2:4:10

F(X i )= f(c2):4:10); writeln(result X i = c2:4:10 F(X i )= f(c2):4:10 n interakciy= nid2); a2:=a2v; b2:=b2v; end; end else writeln('Вы указали что нет необходимости искать отрицательные корни'); end; 2:begin met2_nil; getdate(yer,mon,day,dw); gettime(h,m,s,sc); writeln(result '); writeln(result Metod Nutona. Date: day mon yer h : m); writeln(result Option: Search:

G1:3 polog. korney G2:3 otric. korney. eps: e:1:10); if G1<>0 then begin writeln( Положительные корни:'); writeln(result Polog. korni:'); for i:=1 to G1 do begin met:=1; niton; if (i+1) mod 2=0 then a1:=a1+0.9 else a1:=a1+1.1; writeln('X i = c1:4:10 F(X i )= f(c1):4:10); writeln(result X i = c1:4:10 F(X i )= f(c1):4:10 n interakciy= nin1); end; end else writeln('Вы указали что нет необходимости

искать положительные корни '); if G2<>0 then begin writeln(Отрицательные корни::'); writeln(result Otric. korni:'); for i:=1 to G2 do begin met:=2; niton; if (i+1) mod 2=0 then a2:=a2-0.9 else a2:=a2-1.1; writeln('X i = c2:4:10 F(X i )= f(c2):4:10); writeln(result X i = c2:4:10 F(X i )= f(c2):4:10 n interakciy= nin2); end; end else writeln('Вы указали что нет необходимости искать отрицательные корни'); end; 3:begin met3_nil; getdate(yer,mon,day,dw); gettime(h,m,s,sc); writeln(result

'); writeln(result Metod prostix interakciy. Date: day mon yer h : m); writeln(result Option: Search: G1:3 polog. korney G2:3 otric. korney. eps: e:1:10); if G1<>0 then begin writeln('Положительные корни:'); writeln(result Polog. korni:'); for i:=1 to G1 do begin met:=1; inter; if (i+1) mod 2=0 then begin a1:=a1+0.9; Nint:=1; end else begin a1:=a1+1.1; Nint:=0 end; writeln('X i = c1:4:10

F(X i )= f(c1):4:10); writeln(result X i = c1:4:10 F(X i )= f(c1):4:10 n interakciy= nii1); end; nint:=0; end else writeln('Вы указали что нет необходимости искать положительные корни '); if G2<>0 then begin writeln('Отрицательные корни:'); writeln(result Otric. korni:'); for i:=1 to G2 do begin met:=2; inter; if (i+1) mod 2=0 then begin a2:=a2-0.9; nint:=1; end else begin a2:=a2-1.1; Nint:=0; end; writeln('X i = c2:4:10

F(X i )= f(c2):4:10); writeln(result X i = c2:4:10 F(X i )= f(c2):4:10 n interakciy= nii2); end; end else writeln('Вы указали что нет необходимости искать отрицательные корни' '); end; end; close(result); readln; end. 6.Результаты расчетов. Результаты приведены для первого положительного корня. Метод решения Результат Кол-во итераций Погрешность вычислений

Метод половинного деления X1=1.56519163 15 0.00001 Метод Ньютона X1=1.5651888847 4 0.00001 Метод простых итераций X1=1.5651890039 4 0.00001 7. Графики сходимости. Графики сходимости для первого положительного корня. График сходимости построен по следующей таблице. № интеракции Метод половинного деления Метод Ньютона Метод простых итераций 1 -0,345805753 0,67 0,67 2 0,153708409 0,005562394

-0,014876528 3 -0,098470082 0,01276 9,85267E-05 4 0,027105678 7,54E-08 -1,1252E-06 5 -0,035822101 6 -0,004391149 7 0,01134906 8 0,003477483 9 -0,000457355 10 0,001510535 11 0,000525957 12 3,36929E-05 13 -0,000211233 14 -8,87703E-05 15 -2,75389E-05 8. Выводы Все три метода позволили отыскать необходимое число решений с заданной точностью. Тем не менее все они имеют разную скорость работы, сложность реализации и набор ограничений.

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

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

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