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

21 Содержание : 1.Задание ……………………………………………………… …………………3 2.Теоретическое обоснование методов решения задачи : …………………….4 2.1 Метод половинного деления ………… ……………………………………..4 2.2 Метод Ньютона ……………………………………… ………………………5 2.3 Метод простых и тер аций ……………………………………………………6 3.График исходной функции : ……………………………………………………7 3.1 Общий график функции …………………………………………………….7 3.2 График функции вблизи первого пол корня ………………………………8 3.3 Исходные данные для решения задачи ……………………………………9 4. Блок-схема задачи ……………………………… ……………………………10 5. Исходный текст программы … ……………………………………………..14 6. Результаты расчетов ……………………… …………………………………22 7. Графики сходимости ………………………… ………………………………23 8. Выводы ………………………………………………………… …………….25 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 с шагом 0.01. Данные для построения графика получены из файла data 1. 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 . Локализация первого положительного и первого отрицательного корня , а также т очность вычислений занесены в файл data 2. txt , с которым ра ботает программа. 4. Блок-схема задачи . Упро щенная блок-схема осн овной программы. 21 Упрощенная блок-схема процедуры delenie (метод половинного деления). Данная блок-схема отображает способ нахождения только одного корня уравнения, реальная же процедура delenie способна находить любое число к орней. 21 Упрощенная блок-схем а процедуры niton (метод Ньютона). Данная блок-схема отображает способ нахождения только одного корня ура внения, реальная же процедура niton способна находить любое число корней. 21 Упрощенная блок-схе ма процедуры inter (метод просты х итераций). Данная блок-схема отображает способ нахождения только одног о корня уравнения, реальная же процедура inter способна находить любое число корне й. Итерационная функция имеет вид x = x + f ( x )* l ( x ) = g ( x ) . Анализ производной итерационн ой функции g ( x ) позволил опред елить что функция l ( x ) должна п ринимать значения 1/10 и -1/10 в зависимости от того какой корень рассматривае тся - четный или нечетный, положительный или отрицательный. 21 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-a10 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)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)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)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); a 1:= a 1 v ; b 1:= b 1 v ; 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); a 2:= a 2 v ; b 2:= b 2 v ; 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,666666667 0,666666667 2 0,153708409 0,005562394 -0,014876528 3 -0,098470082 0,000001276 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. Выводы Все три метода позволили отыскать н еобходимое число решений с заданной точностью. Тем не менее все они имеют разную скорость работы, сложность реализации и набор ограничений. Скорость. Наиболее быстрый из всех трех методов-метод Ньютона, немно го уступает ему метод простых итера ций, наиболее медленный метод половинного деления. Сложность реализации. Самым простым в реализации явл яется самый медленный метод-метод половинного деления. Наиболее сложны м является метод простых итераций, это связано в первую очередь с трудно стью выбора итер а ци онной функции. Среднее положение между ними занимает метод Ньютона, осно вная сложность которого заключается в необходимости работы с первой и в торой производной искомой функции. Набор ограничений. Наименее требовательным является метод половинног о деления, при правильном выборе локализации он сходится всегда, однако за это он платит скоростью работы. Метод Ньютона и метод простых итераци й значительно более требовательны к начальным условиям. Так, метод Ньюто на требует достаточно точного приближения к корню, в п ротивном случае он может расходится, а метод простых ит ераций осложняется необходимостью подбора итерацион ной функции, от правильного выбора которой напрямую зависит сходимость метода. Таким образом, можно сделать вывод, что не существует универсального ме тода нахождения корней нелинейного уравнения. Все зависит от конкретны х условий конкретной задачи. В рамках данной курсовой работы наиболее по дходящим методом можно признать метод Ньютона, он наиболее быстрый и в т оже время относительно несложный в реализации.