Вычислительная математика

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Государственное образовательное учреждение

высшего профессионального образования

«Владимирский государственный университет»

Кафедра физики и прикладной математики

Контрольная работа

по дисциплине «Вычислительная математика»

Владимир 2009

Задание 1

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

Метод простых итераций

Отделить корни уравнения х - sinx = 0.25 графически и уточнить один из них методом простых итераций с точностью до 0,001

Теоретические сведения

Как известно, многие уравнения и системы уравнений не имеют аналитических решений.

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

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

Пусть дано уравнение f(x)=0, где:

Функция f(x) непрерывна на отрезке [а, Ь] вместе со своими производными 1-го и 2-го порядка;

Значение f(x) на концах отрезка имеют разные знаки f(a)-f(b)< 0;

Первая и вторая производные f (х) и f (х) сохраняют определённый знак на всем отрезке.

Условия 1 и 2 гарантируют, что на интервале [а, Ь] находится хотя бы один корень, а из условия 3 следует, что f(x) на данном интервале монотонна и поэтому корень будет единственным.

Решить уравнение f(x)=0 итерационным методом значит установить, имеет ли оно корни, сколько корней и найти значения корней с нужной точностью.

Всякое значение ^ , обращающее функцию f(x) в нуль, т.е. такое, что f(Ј) =0, называется корнем уравнения f(x)=0 или нулем функции f(x).

Задача нахождения корня уравнения f(x)=0 итерационным методом состоит из двух этапов:

Отделение корней - отыскание приближенного значения корня или содержащего его отрезка;

Уточнение приближенных корней - доведение их до заданной степени точности.

Расчет

Нормализуем уравнение, т.е. приводим к виду у=х. Дано уравнение: х - sinx = 0.25

Приводим его: x-0.25=sinx

Но корнем уравнения является абсцисса пересечения у = x-0.25 с функцией.

Соответственно у = sinx. Строим ее график.

Рисунок 1.

Из рисунка 1 видно, что точка пересечения графиков, т.е. корень уравнения лежит от 1,0 до 1,5.

Т.к. 0?q?1/2, то lx_n-x_n-1l?0.001.

Данные для ввода в программу:

Начальное приближение = 1,0

Погрешность вычислений = 0,001

Количество итераций = 20

Текст программы

Program Korni;

Uses crt;

Var xi1, xi2, xn1,xn2:real;

Procedure iteracia (x1,x2:real);

Var x3,razn1:real;

Begin

x1:=1; x2:=1;

x2:=0.25+sin(x1);

repeat x3:=0.25+sin(x2);

razn1:=abs(x3)-abs(x2);

if x2>0 then begin

if x3<0 then break;

end;

if x2<0 then begin

if x3>0 then break;

end;

x1:=x2;x2:=x3;

until abs(razn1)<0.001;

xi1:=x3;

xi2:=x3;

x3:=x3+0.001;

xi2:=0.25+sin(x3);

end;

Begin

clrscr;

xi1:=1; xi2:=xi1;

xn1:=1; xn2:=xn1;

iteracia (xi1,xi2);

Writeln(');

end.

Результат работы программы.

- корень методом интераций: 1.17091 и 1.17149

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

Отделить корни уравнения x^3-3x^2+9x-8=0 графически и уточнить один из них методом Ньютона с точностью 0,001.

Теоретические сведения

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

Из уравнения касательной получим расчетную формулу .

Апостериорный критерий окончания итераций .

Расчет

Для отделения корней уравнения x^3-3x^2+9x-8=0 графическим способом построим в одной координатной плоскости графики функций y=x^3 и y=x^2-9*x+8.



Рисунок 2.

Из рисунка 2 видно, что точка пересечения графиков, т.е. корень уравнения x^3-3x^2+9x-8=0 , расположен на отрезке [1;1,5]. В качестве начального приближения х возьмем середину отрезка, т.е x=1.25.

Текст программы

Program Korni;

Uses crt;

Var xn1,xn2,a,e:real;

begin

writeln(' a e ');

readln(a,e);

xn2:=a;

repeat xn1:=xn2;

xn2:=xn1- (xn1*xn1*xn1-3*xn1*xn1+9*xn1-8)/(3*xn1*xn1-6*xn1+9);

until abs(xn2-xn1)<e;

writeln('korni x1 x2');

writeln(' ',xn1:5:3,' ',xn2:5:3);

readkey

end.

езультат работы программы

a e

1 0.001

korni x1 x2

1.167 1.166

Задание 2

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

Решить систему линейных уравнений с точностью

x₁ = 0.23x₁ - 0.04x₂ + 0.21x₃ - 0.18x₄ + 1.24

x₂ = 0.45x₁ - 0.23x₂ + 0.06x₃ - 0.88

x₃ = 0.26x₁ + 0.34x₂ - 0.11x₃ + 0.62

x₄ = 0.05x₁ - 0.26x₂ + 0.34x₃ - 0.12x₄ - 1.17

Теоретическая часть

Приведем решаемую систему эквивалентным преобразованием к виду .

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

Отсюда находим:

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

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

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

Итерационный процесс метода простой итерации описывается формулой:

(1)

где - некоторое начальное приближение к решению (обычно берут ).

В координатной форме метод простой итерации записывается следующим образом:

Таким образом -ая компонента -го приближения к решению вычисляется по формуле:

Program sistema;

Uses crt;

Var x1,xn1,x2,xn2,x3,xn3,x4,xn4,p1,t1,p2,t2,p3,t3,p4,t4:real;

e:real; n:integer;

Begin

clrscr;

n:=0;

x1:=-10; x2:=x1;x3:=x2;x4:=x3;

repeat xn1:=0.23*x1-0.04*x2+0.21*x3-0.18*x4+1.24;

xn2:=0.45*x1-0.23*x2+0.06*x3-0.88;

xn3:=0.26*x1+0.34*x2-0.11*x3+0.62;

xn4:=0.05*x1-0.26*x2+0.34*x3-0.12*x4-1.17;

p1:=abs(xn1)-abs(x1);

p2:=abs(xn2)-abs(x2);

p3:=abs(xn3)-abs(x3);

p4:=abs(xn4)-abs(x4);

n:=n+1;

e:=abs(p1)+abs(p2)+abs(p3)+abs(p4);

x1:=xn1; x2:=xn2; x3:=xn3; x4:=xn4;

until e<0.001;

Writeln(');

writeln(' ');

write('Корни уравнения: ');

writeln (x1:1:3,'; ',x2:1:3,'; ',x3:1:3,'; ',x4:1:3);

writeln(' ');

write('Точность вычисления (значение предела): ');

writeln (p1:1:5,'; ',p2:1:5,'; ',p3:1:5,'; ',p4:1:5);

end.

Результат работы программы.

Корни уравнения: 2.048; 0.086; 1.065; -0.650

Точность вычисления (значение предела): -0.00005; 0.00026; 0.00022; 0.00017

Задание 3

Интерполяция

Интерполяция функции с помощью полинома Лагранжа

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

Количество узлов в таблице = 6, т.к. 6 строк в исходной таблице.

Количество точек интерполяции = 3, т.к. из условия только три точки (правая таблица в задании).

Теоретическая часть

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

.

Свободные параметры определяются из системы.

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

Рассмотрим процесс построения интерполяционного полинома Лагранжа.

Пусть функция задана в узлах, произвольно расположенных на отрезке : , , …, .

Требуется найти многочлен степени не выше :

.

,

где - коэффициенты, зависящие от узлов и текущего значения . Этим условиям отвечают коэффициенты вида:

.

Для интерполяционного полинома Лагранжа получим:

.

Расчет

Program zad_Langranj;

Uses crt;

Type tv=array [1..6] of real;

itv=array [1..3] of real;

Var xtv, ytv, p:tv; ix,iy:itv; a,b:integer; l,p1,m:real;

Begin

clrscr;

for a:=1 to 6 do begin

write('Введите значение х[',a,']= ');

readln(l);

xtv[a]:=l;

end;

writeln(' ');

for a:=1 to 6 do begin

write('Введите значение y[',a,']= ');

readln(l);

ytv[a]:=l;

end;

writeln(' ');

for a:=1 to 3 do begin

write('Введите значение для х[',a,']= ');

readln(l);

ix[a]:=l;

end;

for a:=1 to 6 do begin

l:=xtv[a];

p1:=(l-xtv[2])*(l-xtv[3])*(l-xtv[4])*(l-xtv[5])*(l-xtv[6]);

p1:=p1+(l-xtv[1])*(l-xtv[3])*(l-xtv[4])*(l-xtv[5])*(l-xtv[6]);

p1:=p1+(l-xtv[1])*(l-xtv[2])*(l-xtv[4])*(l-xtv[5])*(l-xtv[6]);

p1:=p1+(l-xtv[1])*(l-xtv[2])*(l-xtv[3])*(l-xtv[5])*(l-xtv[6]);

p1:=p1+(l-xtv[1])*(l-xtv[2])*(l-xtv[3])*(l-xtv[4])*(l-xtv[6]);

p1:=p1+(l-xtv[1])*(l-xtv[2])*(l-xtv[3])*(l-xtv[4])*(l-xtv[5]);

p[a]:=p1;

end;

for a:=1 to 3 do begin

iy[a]:=0;

m:=(ix[a]-xtv[1])*(ix[a]-xtv[2])*(ix[a]-xtv[3])*(ix[a]-xtv[4]);

m:=m*(ix[a]-xtv[5])*(ix[a]-xtv[6]);

for b:=1 to 6 do begin

l:=(ytv[b]*m)/(p[b]*(ix[a]-xtv[b]));

iy[a]:=iy[a]+l;

end;

end;

clrscr;

writeln('');

writeln(' ');

for a:=1 to 3 do begin

writeln('Значение х= ',ix[a]:2:3,'

соответствующее значение y= ',iy[a]:2:5);

end;

writeln(' ');

for a:=1 to 6 do begin

writeln('x[',a,']= ',xtv[a]:2:2,' y[',a,']= ',ytv[a]:2:4);

end;

end.

Результат работы программы.

Значение х= 0.702 соответствующее значение y= 2.23357

Значение х= 0.512 соответствующее значение y= 1.79697

Значение х= 0.645 соответствующее значение y= 2.09249

x[1]= 0.43 y[1]= 1.6360

x[2]= 0.48 y[2]= 1.7323

x[3]= 0.55 y[3]= 1.8769

x[4]= 0.62 y[4]= 2.0334

x[5]= 0.70 y[5]= 2.2285

x[6]= 0.75 y[6]= 2.3597

Интерполяция функции с помощью полинома Ньютона

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

если функция задана в равноотстоящих узлах таблицы.

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

Шаг изменения аргумента - это разность между i-м элементом этой таблицы с i-1 элементом.

Теоретическая часть

В большинстве случаев функция задается в равноотстоящих узлах так, что , где - шаг интерполяции.

В этом случае применяется полином Ньютона, использующий конечные разности. Конечной разностью первого порядка в точке называется разность , где , . Используя конечные разности первого порядка можно получить конечные разности второго порядка .

Определив коэффициенты получим:

.

Для программной реализации расчета коэффициентов полинома ньютона используют следующие формулы:

Расчет

Program zad_Nuton;

Uses crt;

Type tv=array [1..6] of real; ttv=array [1..5] of real;

ttv2=array [1..4] of real; ttv3=array[1..3] of real;

ttv4=array[1..2] of real;

Var ix, iy:tv; p1:ttv; p2:ttv2; p3, xc,yc:ttv3;

iy4:ttv4; iy5, s,h,t:real; i,j,c:integer; z:array[1..3] of integer;

Begin

clrscr;

for i:=1 to 6 do begin

write('Введите значение х[',i,']= ');

readln(ix[i]);

end;

writeln(' ');

for i:=1 to 6 do begin

write('Введите значение y[',i,']=');

readln(iy[i]);

end;

for i:=1 to 5 do begin

s:=iy[i+1]-iy[i];

p1 [i]:=s;

end;

for i:=1 to 4 do begin

s:=p1[i+1]-p1[i];

p2[i]:=s;

end;

for i:=1 to 3 do

p3[i]:=p2[i+1]-p2[i];

for i:=1 to 2 do

iy4[i]:=p3[i+1]-p3[i];

iy5:=iy4[2]-iy4[1];

h:=ix[2]-ix[1];

writeln(' ');

for i:=1 to 3 do begin

write('Введите значение для x[',i,']= ');

readln(xc[i]);

end;

for i:=1 to 3 do begin

for j:=2 to 6 do begin

if (xc[i]>ix[j]) and(xc[i]<ix[j]) then z[i]:=j-1;

end;

end;

for i:=1 to 3 do begin

j:=6-z[i];

t:=(xc[i]-ix[z[i]])/h;

yc[i]:=iy[z[i]]+t*p1[z[i]];

if j>=2 then yc[i]:=yc[i]+(t*(t-1)*p2[z[i]])/2;

if j>=3 then yc[i]:=yc[i]+(t*(t-1)*(t-2)* p3[z[i]])/6;

if j>=4 then yc[i]:=yc[i]+(t*(t-1)*(t-2)*(t-3)* iy4[z[i]])/24;

if j=5 then yc[i]:=yc[i]+(t*(t-1)*(t-2)*(t-3)*(t-4)* iy5)/120;

end;

clrscr;

writeln(' ');

writeln ('');

writeln(' ');

for i:=1 to 3 do begin

writeln('Для х[',i,']= ',xc[i]:2:4,' значение у[',i,']= ',yc[i]:2:5);

end;

writeln(' ');

writeln (' ИСХОДНЫЕ ДАННЫЕ:');

writeln(' ');

for i:=1 to 6 do begin

writeln('Для х[',i,']= ',ix[i]:2:3,' значение у[',i,']= ',iy[i]:2:5);

end;

end.

Результат работы программы.

Для х[1]= 1.3832 значение у[1]= 5.26791

Для х[2]= 1.3926 значение у[2]= 5.55226

Для х[3]= 1.3862 значение у[3]= 5.35555

ИСХОДНЫЕ ДАННЫЕ:

Для х[1]= 1.375 значение у[1]= 5.04192

Для х[2]= 1.380 значение у[2]= 5.17744

Для х[3]= 1.385 значение у[3]= 5.32016

Для х[4]= 1.390 значение у[4]= 5.47069

Для х[5]= 1.395 значение у[5]= 5.62968

Задание 4

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

Теоретические сведения

Если таблично заданная функция у = f{x) отображает результаты эксперимента, то нецелесообразно, что бы аппроксимирующая функция ф(х) в точности повторяла значения fj, содержащие погрешности измерений.

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

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

Для определения коэффициентов aj этого многочлена может быть применен критерий, состоящий в минимизации функции Е = F(eo ,ei ,...,e_m), где ei - отклонения аппроксимирующей функции от заданных значений ei = (p(Xj)-fi.

Расчет

Количество узлов таблицы = количеству ее строк = 20.

Количество строк в таблице = 20. В каждой строке X рассчитывается, как номер строки умножить на 0.1, т.е. например для первой строки Х = 1*0.1=0.1, для второй строки X = 2 * 0.1 = 0.2 для третьей - X = 3 * 0.1 = 0.3 и т.д. И вводим соответствующее значение У в данной строке.

Program zad_Approximacia;

Uses crt;

Type

tv=array[1..20] of real;

tv2=array [1..7] of real;

Var x,y,x2,x3,x4,xy,xy2:tv; w:tv2;

j:integer; m,d,dx,dy,dz,xi,yi,zi:real;

Begin

clrscr;

for j:=1 to 20 do begin

write('Введите значение y[',j,']=');

readln(m);

x[j]:=j*0.1;

y[j]:=m;

x2[j]:=x[j]*x[j];

x3[j]:=x2[j]*x[j];

x4[j]:=x3[j]*x[j];

xy[j]:=x[j]*y[j];

xy2[j]:=x2[j]*y[j];

end;

for j:=1 to 20 do begin

w[1]:=w[1]+x[j];

w[2]:=w[2]+x2[j];

w[3]:=w[3]+x3[j];

w[4]:=w[4]+x4[j];

w[5]:=w[5]+y[j];

w[6]:=w[6]+xy[j];

w[7]:=w[7]+xy2[j];

end;

{clrscr;}

d:=w[2]*(w[2]*w[2]-w[3]*w[1])-w[1]*(w[3]*w[2]-w[4]*w[1]);

d:=d+20*(w[3]*w[3]-w[4]*w[2]);

dx:=w[5]*(w[2]*w[2]-w[3]*w[1])-w[1]*(w[6]*w[2]-w[7]*w[1]);

dx:=dx+20*(w[6]*w[3]-w[7]*w[2]);

dy:=w[2]*(w[6]*w[2]-w[7]*w[1])-w[5]*(w[3]*w[2]-w[4]*w[1]);

dy:=dy+20*(w[3]*w[7]-w[4]*w[6]);

dz:=w[2]*(w[2]*w[7]-w[3]*w[6])-w[1]*(w[3]*w[7]-w[4]*w[6]);

dz:=dz+w[5]*(w[3]*w[3]-w[4]*w[2]);

if d=0 then begin

writeln('Делитель системы=0');

end;

xi:=dx/d;

yi:=dy/d;

zi:=dz/d;

writeln(' ');

writeln('');

writeln(' ');

writeln (' Функция: ',xi:1:3,'x2+',yi:1:3,'x+',zi:1:3);

end.

Результат работы программы.

Введите значение y[1]=2.05

Введите значение y[2]=1.94

Введите значение y[3]=1.92

Введите значение y[4]=1.87

Введите значение y[5]=1.77

Введите значение y[6]=1.88

Введите значение y[7]=1.71

Введите значение y[8]=1.60

Введите значение y[9]=1.56

Введите значение y[10]=1.40

Введите значение y[11]=1.50

Введите значение y[12]=1.26

Введите значение y[13]=0.99

Введите значение y[14]=0.97

Введите значение y[15]=0.91

Введите значение y[16]=0.71

Введите значение y[17]=0.43

Введите значение y[18]=0.54

Введите значение y[19]=0.19

Введите значение y[20]=0.01

Функция: -0.429x2+-0.132x+2.015

Задание 5

Вычисление интеграла по формуле трапеций с тремя десятичными знаками

Теоретическая часть

Заменим подынтегральную функцию на отрезке полиномом первой степени :

,

где и - значение и конечная разность первого порядка функции в точке .

В этом случае приближенное значение интеграла определяется площадью трапеции:

.

На основе этой формулы можно получить приближенную формулу для вычисления интеграла:

.

Погрешность метода трапеций на одном интервале определяется по формуле:

.

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

.

Метод трапеций имеет второй порядок точности.

program integ;

uses crt;

type t=array[0..8] of real;

var x,s,a,b,h,unteg: real; i,j: integer;

y: t;

begin

writeln('vvedite a b h ');

readln(a,b,h);

x:=a;

y[0]:=1/sqrt(2*x*x+1);

repeat x:=x+h;

for i:=1 to 8 do

y[i]:=1/sqrt(2*x*x+1);

s:=0;

for j:=1 to 7 do begin

s:=s+y[j] ;

writeln('s=',s:5:3);

end

until x>=b;

unteg:=h*(y[0]+y[8]+2*s);

writeln ('unteg= ',unteg:5:3);

readkey

end.

Результаты работы программы

s=2.867

s=3.345

s=0.451

s=0.902

s=1.353

s=1.803

s=2.254

s=2.705

s=3.156

s=0.426

s=0.853

s=1.279

s=1.706

s=2.132

s=2.558

s=2.985

s=0.404

s=0.808

s=1.213

s=1.617

s=2.021

s=2.425

s=2.830

unteg= 0.673

Вычисление интеграла по формуле Симпсона

Вычислить интеграл по формуле Симпсона при п -- 8; оценить погрешность результата, составив таблицу конечных разностей.

Теоретическая часть

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

,

где - погрешность вычисления интеграла.

Для записи полинома воспользуемся интерполяционной формулой для трех узлов :

,

где - значение и конечные разности первого и второго порядков функции в точке .

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

.

На основе этой формулы можно получить приближенную формулу для вычисления интеграла:

.

Погрешность метода трапеций на одном интервале определяется по формуле:

.

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

.

Метод трапеций имеет четвертый порядок точности.

Для оценки погрешности метода Симпсона можно составить таблицу конечных разностей и применить формулу:

Program zad_Simpson;

Uses crt;

Type t=array [0..8] of real;

Var x,y:t; n:integer; p,lg,lg2,pg:real;

Begin

clrscr;

p:=1.2;

for n:=0 to 8 do begin

y[n]:=0.43429*ln(p+2)/p;

x[n]:=p;

p:=p+1.35;

end;

writeln('');

writeln(' ');

for n:=0 to 8 do begin

writeln('Для Х',n,'=',x[n]:1:2,' Y',n,'=',y[n]:1:5);

end;

lg:=1.35/3*(y[0]+y[8]+4*(y[1]+y[3]+y[5]+y[7])+2*(y[2]+y[4]+y[6]));

lg2:=1.35*2/3*(y[0]+y[8]+4*(y[2]+y[6])+2*y[4]);

pg:=(lg-lg2)/15;

writeln(' ');

writeln('Результат вычислений= ',lg:1:7);

writeln(' ');

writeln('Точность вычисления (удвоение шага)= ',pg:1:11);

end. уравнение интеграл функция трапеция

Результаты работы программы

Для Х0=1.20 Y0=0.42095

Для Х1=2.55 Y1=0.25804

Для Х2=3.90 Y2=0.19765

Для Х3=5.25 Y3=0.16387

Для Х4=6.60 Y4=0.14159

Для Х5=7.95 Y5=0.12551

Для Х6=9.30 Y6=0.11323

Для Х7=10.65 Y7=0.10348

Для Х8=12.00 Y8=0.09551

Результат вычислений= 1.8112664

Точность вычисления (удвоение шага)= -0.00183992680

Задание 6

Оптимизация функции

Теоретическая часть

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

Определение. Золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка.

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

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

1. Точка производит золотое сечение отрезка , так как и . Аналогично точка производит золотое сечение отрезка .

2. Для точек золотого сечения выполняется равенство:

.

Алгоритм метода золотого сечения заключается в следующем. Положим . На отрезке возьмем точки , производящие золотое сечение, и вычислим значения . Далее, если , то примем . Если же , то . Здесь важно то, что внутри нового отрезка уже содержится точка , которая производит золотое сечение этого отрезка. Причем, в этой точке уже известно значение функции . Длина отрезка

.

Опишем -й шаг алгоритма. Пусть уже определены точки , вычислены значения , найден отрезок такой, что , и известна точка , производящее золотое сечение отрезка , . Тогда в качестве следующей точки возьмем точку , которая в силу свойства (2) также производит золотое сечение отрезка . Вычислим значение . Пусть для определенности (случай рассматривается аналогично). Если , то полагаем ; если же , то . Новый отрезок таков, что , , точка производит золотое сечение отрезка и .

Одномерная оптимизация функции методом дихотомии.

Графически определить точку экстремума функции f(x), т. е. найти отрезок [а; Ь], на котором лежит точка экстремума.

Оптимизировать функцию методом дихотомии.

Строим график функции. Определяем границы, где функция принимает минимальное значение. Возьмем [2,3].

Ширина интервала неопределенности. Выбираем любое значение, но помним, что чем

меньше ширина интервала, тем точнее результат. Например, возмем 0.00001.

Текст программы.

Program min;

Uses crt;

Var a,b,e,x:real;

function f(x:real):real;

begin

f:=x*x/2+5*cos(x);

end;

procedure gold(a,b,e:real; var x:real);

const g=0.618034;

var x1,x2,f1,f2,r:real;

begin writeln('x1 x2 f1 f2');

r:=(b-a)*g; x1:=a+r; f1:=f(x1) ;x2:=b-r; f2:=f(x2);

while r>e do begin r:=r*g;

if f1<f2 then begin

x:=x2+r; x2:=x1; f2:=f1; f1:=f(x);x1:=x

end else begin x:=x1-r; x1:=x2; f1:=f2;f2:=f(x); x1:=x

end;

writeln(' ',x1:5:2,' ',x2:5:2,' ',f1:5:2,' ',f2:5:2);

end

end;

begin

write (' a,b,e'); readln(a,b,e);

gold(a,b,e,x);writeln('f(',x:3:5,')=',f(x):3:5);

readkey

end.

Результат работы программы.

Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International

a,b,e 2 3.5 0.001

x1 x2 f1 f2

2.35 2.57 -0.90 -0.76

2.93 2.35 -0.60 -0.90

2.71 2.35 -0.90 -0.87

2.49 2.71 -0.88 -0.90

2.41 2.71 -0.90 -0.81

2.76 2.41 -0.83 -0.90

2.73 2.41 -0.90 -0.86

2.43 2.73 -0.83 -0.90

2.41 2.73 -0.90 -0.82

2.74 2.41 -0.85 -0.90

2.73 2.41 -0.90 -0.86

2.42 2.73 -0.82 -0.90

2.41 2.73 -0.90 -0.82

2.73 2.41 -0.85 -0.90

2.73 2.41 -0.90 -0.86

f(2.73124)=-0.85507

Размещено на Allbest.ru

...