Исследование методов решения линейных уравнений
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
нтервала имеет значения разных знаков, то внутри этого интервала у нее есть корень (как минимум, один, но м.б. и несколько)". Вот на базе этой теоремы и построено численное нахождение приближенного значения корня функции. Обобщенно этот метод называется "дихотомией", т.е. "делением отрезка на две части". Обобщенный алгоритм выглядит так:
задать начальный интервал [a;b];
убедиться, что на концах функция имеет разный знак
< 0.;
Начальное приближение
= .
повторять
выбрать внутри интервала точку X;
сравнить знак функции в точке X со знаком функции в одном из концов;
если совпадает, то переместить этот конец интервала в точку X,
иначе переместить в точку X другой конец интервала;
После каждой итерации отрезок, содержащий корень уменьшается вдвое;
пока не будет достигнута нужная точность.
"Нужная точность" определяется условиями задачи. Иногда требуется, чтобы значение функции было меньше некой наперед заданной величины, но это редко - чаще всего требуется определить значение корня с отклонением от истинного в заданных пределах. Лучше всего, если можно с уверенностью гарантировать интервал, в котором находится корень.
Метод выбора точки деления - ключевой для скорости работы метода. Хорошо, если функция, чей корень находится, проста и быстро вычисляется; но внутри функции могут быть и матричные операции, и численное интегрирование, и все что угодно; так что главным критерием оптимизации является минимизация числа делений (естественно, без ухудшения точности метода).
Метод деления пополам позволяет исключать в точности половину интервала на каждой итерации. При использовании метода считается, что функция непрерывна и имеет на концах интервала разный знак. После вычисления значения функции в середине интервала одна часть интервала отбрасывается так, чтобы функция имела разный знак на концах оставшейся части. Инерционный процесс продолжается до тех пор, пока длина полученного отрезка не станет меньше заданной величины . За приближенное решение принимается средняя точка последнего промежутка.
Метод золотого сечения
Метод золотого сечения позволяет исключать интервалы, вычисляя только одно значение функции на каждой итерации. В результате двух рассмотренных значений функции определяется интервал, который должен использоваться в дальнейшем. Этот интервал будет содержать одну из предыдущих точек и следующую точку, помещаемую симметрично ей. Точка делит интервал на две части так, что отношение целого к большей части равно отношению большей части к меньшей, т. е. равно так называемому золотому сечению.
Воспользуемся соотношением
Lj-1 = Lj + Lj+1.
Будем поддерживать постоянными отношения длин интервалов
Lj-1 / Lj = Lj / Lj+1 = ?.
Это уравнение имеет единственный положительный корень ? = (1+5^1/2) / 2= 1.618 (рис.9). первые 2 эксперимента
Рис.9
находятся на расстоянии 0.618 от концов отрезка. По результатам экспериментов сохраняется 1 из интервалов, и все повторяется. После n экспериментов
Ln = 1/ ?n-1.
Поиск с помощью метода золотого сечения является асимптотически наиболее эффективным способом реализации минимаксной стратегии поиска, так как требует наименьшего числа оценки значения функции для достижения заданной точности по сравнению с другими методами исключения интервалов.
Листинг программы по методу пассивного поиска, методу дихотомии, методу золотого сечения, оптимальный поиску
0)theninc(N);odd(N)theninc(N);">function TMyForm.F(x:real):real;:=(2*x-2)*(2*x-2)+2;TMyForm.PasPoisk(XMax,XMin,Eps,D:Real):string;: word;: word;: word;: real;: array[word] of real;:=trunc((2*(XMax-XMin))/Epsilon);(frac((2*(XMax-XMin))/Epsilon)<>0) then inc(N);odd(N) then inc(N);
x[1]:=XMin;[N]:=XMax;
f(x[i]))thenIndex:=i;i:=1toNdochGraph.Series[0].AddXY(x[i],f(x[i]),,clBlue);.Series[1].AddXY(x[Index],f(x[Index]),,clRed);:=FloatToStr(x[Index])+;=+IntToStr(N)+.;TMyForm.Dihotomy(XMax,XMin,Eps,D:Real):string;:word;:array[1..4]ofreal;[1]:=XMin;[4]:=XMax;:=2;.Series[0].AddXY(x[1],f(x[1]),,clAqua);.Series[0].AddXY(x[4],f(x[4]),,clAqua);((abs(x[4]-x[1])/2)>Eps)do[2]:=((x[4]-x[1])/2)-D;[3]:=((x[4]-x[1])/2)+D;(N,2);.Series[0].AddXY(x[2],f(x[2]),,clAqua);.Series[0].AddXY(x[2],f(x[3]),,clAqua);(f(x[3])>f(x[2]))thenx[4]:=x[3]x[1]:=x[2];.Series[1].AddXY((x[1]+x[4])/2,f((x[1]+x[4])/2),,clRed);:=FloatToStr((x[1]+x[4])/2)+;=+IntToStr(N);TMyForm.GoldSection(XMax,XMin,Eps,D:Real):string;Tau=0.618;:byte;:word;:array[1..4]ofReal;:array[1..4]ofReal;[1]:=XMin;[4]:=XMax;[2]:=XMax-Tau*(XMax-XMin);">temp:=XMin;i:=1 to (N div 2 - 1) do:=temp+(XMax-XMin)/(N/2);[2*i]:=temp-D;[2*i+1]:=temp+D;:=1;i:=2 to N do(f(x[Index])>f(x[i])) then Index:=i;i:=1 to N do chGraph.Series[0].AddXY(x[i],f(x[i]),,clBlue);.Series[1].AddXY(x[Index],f(x[Index]),,clRed);:=FloatToStr(x[Index])+; Количество итераций = +IntToStr(N)+.;TMyForm.Dihotomy(XMax,XMin,Eps,D:Real):string;: word;: array [1..4] of real;[1]:=XMin;[4]:=XMax;:=2;.Series[0].AddXY(x[1],f(x[1]),,clAqua);.Series[0].AddXY(x[4],f(x[4]),,clAqua);((abs(x[4]-x[1])/2)>Eps) do[2]:=((x[4]-x[1])/2)-D;[3]:=((x[4]-x[1])/2)+D;(N,2);.Series[0].AddXY(x[2],f(x[2]),,clAqua);.Series[0].AddXY(x[2],f(x[3]),,clAqua);(f(x[3])>f(x[2])) then x[4]:=x[3]x[1]:=x[2];.Series[1].AddXY((x[1]+x[4])/2,f((x[1]+x[4])/2),,clRed);:=FloatToStr((x[1]+x[4])/2)+; Количество итераций = +IntToStr(N);TMyForm.GoldSection(XMax,XMin,Eps,D:Real):string;Tau=0.618;: byte;: word;: array[1..4] of Real;: array[1..4] of Real;[1]:=XMin;[4]:=XMax;[2]:=XMax-Tau*(XMax-XMin);
x[3]:=XMin+Tau*(XMax-XMin);
Epsdoy[3]>y[2]then[4]:=x[3];y[4]:=y[3];[3]:=x[2];y[3]:=y[2];[2]:=x[4]-Tau*(x[4]-x[1]);[2]:=f(x[2]);.Series[0].AddXY(x[2],y[2],,clRed);(N)[1]:=x[2];y[1]:=y[2];[2]:=x[3];y[2]:=y[3];[3]:=x[1]-Tau*(x[4]-x[1]);[3]:=f(x[3]);.Series[0].AddXY(x[3],y[3],,clRed);(N);.Series[1].AddXY((x[1]+x[4])/2,f((x[1]+x[4])/2),,clBlue);:=FloatToStr((x[4]+x[1])/2)+;=+IntToStr(N);TMyForm.OptPoisk(XMax,XMin,Eps,D:Real):string;fb:array[byte]ofword;:array[1..4]ofreal;:array[byte]ofreal;:byte;:word;[1]:=XMin;">for i:=1 to 4 do y[i]:=f(x[i]);i:=1 to 4 do chGraph.Series[0].A