Комплексное исследование численных методов для задачи решения нелинейных уравнений

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

1. Постановка задачи

Провести комплексное исследование численных методов для задачи решения нелинейных уравнений.

1. Решить нелинейные уравнения

а) ;

б) ;

в) .

2. Использовать для решения

а) метод золотого сечения;

б) метод дихотомии;

в) метод простых итераций.

3. Общее оформление пояснительной записки.

2. Основные сведения

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

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

Золотое сечение, открытое Евклидом, состоит в разбиении интервала (a;b). Точкой на две части таким образом, чтобы отношение длины всего интервала к большей части было равно отношению большей части к меньшей: Легко проверить, что золотое сечение производят две точки:

x1=a+(1-t)(b-a)

x2=a+t(b-a)

При t=0.618.

Алгоритм метода золотого сечения следующий:

1) вычисляют значения x1 и x2;

2) вычисляют f(x1) и f(x2);

3) если f(x1) < f(x2) , то для дальнейшего деления оставляют интервал [a;x2];

4) если f(x1) > f(x2), то для дальнейшего деления оставляют интервал[x1;b].

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

Точка производящая золотое сечение интервала, точка - интервала . Поэтому на оставшемся интервале нужно определить только одну точку, производящую золотое сечение.

3.1 Решение уравнения

Метод дихотомии.

Программа для решения данным методом написана на языке программирования С++. Для поиска интервалов х, в которых функция имеет разные знаки задается цикл, поиск производится начиная с х=0.00001 и продолжается до х=100. (Так как lg(x) - функция, аргумент х которой не может принимать отрицательные значения и не может быть равен нулю.).

Листинг 1. - решение уравнения методом дихотомии.

//прога решает нелинейное уравнение методом дихотомии

#include<stdlib.h>

#include<iostream.h>

#include<conio.h>

#include<math.h>

int main()

{

clrscr();

double x,x1,y,y1,X[5],Y[5],s;

int n,i;

char l;

x=0.00001;//задаем начальное приближение

y=2*x+log10(x)+0.5;

n=1;

cout.setf(ios::fixed);//флаг вывода чисел в формате с фиксированной запятой

cout.setf(ios::showpoint);

cout.precision(10);// вывод чисел с пятью знаками после запятой

for(x1=0.00001;x1<=100;x1++)//начинаем проверку графика на интервалы в которых функция имеет разные знаки с шагом 1

{

y1=2*x1+log10(x1)+0.5;

if((y*y1)<0)

{

X[n]=x1;//если знак функции меняется, то записываем данную точку в массив

Y[n]=y1;

cout << "X[" << n << "]=" << X[n] << endl;

cout << "Y[" << n << "]=" << Y[n] << endl;

n++;

}

y=y1;

x=x1;

}

X[0]=(X[1]-1);//инициализируем первую точку

Y[0]=2*X[0]+log10(X[0])+0.5;

n=1;

double X1[]={X[0], X[1], X[1], X[2]};//инициализируем массив, удобный для работы

double Y1[]={Y[0], Y[1], Y[1], Y[2]};

do//цикл вычисления корня

{

x=(X1[0]+X1[1])/2;

y=2*x+log10(x)+0.5;

if((Y1[0]*y)>0)//заменяем границы интервала

{

X1[0]=x;

Y1[0]=y;

}

else

{

X1[1] = x;

Y1[1] = y;

}

n++;

s=y;

}while(fabs(s)>0.000001);//задаем точность

cout << "x1="<< x << "" <<"n1=" << n <<endl;//выведем полученное решение и количество итераций

cout << "s=" << s << endl;

s=n=1;

getch();

return 0;

}

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

X[1]=1.0000100000

Y[1]=2.5000243429

x1=0.1549310548n1=22

s=0.0000005874

Как мы видим данное уравнение имеет один корень х=0.1549310548.

В программе задавалась точность решения задачи до шестого знака после запятой. При подстановке данного значения х в уравнение мы получили значение s=0.0000005874, то есть практически равное нулю, с заданной нами точностью.

Из графика функции, построенного в Mathcad видно, что уравнение имеет один корень, примерно в заданном промежутке:



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

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

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

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

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

Листинг 2. - Программа на языке С++ для решения уравнения методом простых итераций.

#include<iostream.h>

#include<conio.h>

#include<math.h>

int main()

{

clrscr();

long double x, x1, y=1;

int n=1;

x=1;

do//цикл вычисления корня

{

x1=pow(10,(-2*x-0.5));//находим хi

x=x1;//заменяем для следующего цикла

y=2*x+log10(x)+0.5;//проверяем на равенство нулю

n++;//счетчик циклов

}while(fabs(y)>0.0001);//задаем точность

cout << "x=" << x << "\ny=" << y << "n=" << n << endl;

getch();

return 0;

}

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

x=0.154929

y=-8.480816e-06n=36

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

В данном методе нам понадобилось больше циклов для достижения заданной точности.

Метод золотого сечения.

В данном методе, как и в методе дихотомии мы сначала проверяем функцию на интервалы, в которых знак ее меняется, начиная с х=0.00001. Точность вычислений находим как модуль разности х1 и х2 .

Листинг 3. - Программа на языке С++ для решения уравнений методом золотого сечения.

//прога решает нелинейное уравнение методом золотого сечения

#include<stdlib.h>

#include<iostream.h>

#include<conio.h>

#include<math.h>

int main()

{

clrscr();

double x,x1,x2,y,y1,y2,X[5],Y[5],s,t;

int n,i;

char l;

t=0.618;

x=0.00001;

y=2*x+log10(x)+0.5;

n=1;

cout.setf(ios::fixed);//флаг вывода чисел в формате с фиксированной запятой

cout.setf(ios::showpoint);

cout.precision(10);// вывод чисел с пятью знаками после запятой

for(x1=0.00001;x1<=100;x1++)//начинаем проверку графика на интервалы в которых функция имеет разные знаки с шагом 1

{

y1=2*x1+log10(x1)+0.5;

if((y*y1)<0)

{

X[n]=x1;//если знак функции меняется, то записываем данную точку в массив

Y[n]=y1;

cout << "X[" << n << "]=" << X[n] << endl;

cout << "Y[" << n << "]=" << Y[n] << endl;

n++;

}

y=y1;

x=x1;

}

X[0]=(X[1]-1);//инициализируем первую точку

Y[0]=2*X[0]+log10(X[0])+0.5;

n=1;

double X1[]={X[0], X[1], X[1], X[2], X[2], X[3], X[3], X[4]};//инициализируем массив, удобный для работы

double Y1[]={Y[0], Y[1], Y[1], Y[2], Y[2], Y[3], Y[3], Y[4]};

do//цикл вычисления корня

{

x1=X1[0]+(1-t)*(X1[1]-X1[0]);

x2=X1[0]+t*(X1[1]-X1[0]);

y1=2*x1+log10(x1)+0.5;

y2=2*x2+log10(x2)+0.5;

if(fabs(y1)<fabs(y2))//заменяем границы интервала

{

X1[1]=x2;

}

else

{

X1[0] = x1;

}

n++;

s=fabs(x1-x2);

}while(fabs(s)>0.00001);//задаем точность

x=x1+t*(x2-x1);

y=2*x+log10(x)+0.5;

cout << "x1="<< x << "" <<"n1=" << n <<endl;//выведем полученное решение и количество итераций

cout << "y=" << y << endl;

getch();

return 0;

}

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

X[1]=1.0000100000

Y[1]=2.5000243429

x1=0.1549436363n1=23

y=0.0000610168

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

3.2 Решение уравнения

алгоритм уравнение программа

Для оценки точности решения и количества корней уравнения сначала построим график в пакете Mathcad.

Как мы видим, уравнение имеет один корень в интервале [1;1.5].

Метод дихотомии.

Для нахождения промежутков перемены знака мы задаем цикл, в котором проверяем значения у, подставляя в уравнение значения х от -100 до 100 с шагом 1.

Листинг 4.- Программа для решения уравнения методом дихотомии.

//прога решает нелинейное уравнение методом дихотомии

#include<stdlib.h>

#include<iostream.h>

#include<conio.h>

#include<math.h>

int main()

{

clrscr();

double x,x1,y,y1,X[5],Y[5],s;

int n,i;

char l;

x=-100;

y=pow(x,3)-3*pow(x,2)+6*x-5;

n=1;

cout.setf(ios::fixed);//флаг вывода чисел в формате с фиксированной запятой

cout.setf(ios::showpoint);

cout.precision(10);// вывод чисел с пятью знаками после запятой

for(x1=-100;x1<=100;x1++)//начинаем проверку графика на интервалы в которых функция имеет разные знаки с шагом 1

{

y1=pow(x1,3)-3*pow(x1,2)+6*x1-5;

if((y*y1)<0)

{

X[n]=x1;//если знак функции меняется, то записываем данную точку в массив

Y[n]=y1;

cout << "X[" << n << "]=" << X[n] << endl;

cout << "Y[" << n << "]=" << Y[n] << endl;

n++;

}

y=y1;

x=x1;

}

X[0]=(X[1]-1);//инициализируем первую точку

Y[0]=pow(X[0],3)-3*pow(X[0],2)+6*X[0]-5;

n=1;

double X1[]={X[0], X[1], X[1], X[2], X[2], X[3], X[3], X[4]};//инициализируем массив, удобный для работы

double Y1[]={Y[0], Y[1], Y[1], Y[2], Y[2], Y[3], Y[3], Y[4]};

do//цикл вычисления корня

{

x=(X1[0]+X1[1])/2;

y=pow(x,3)-3*pow(x,2)+6*x-5;

if((Y1[0]*y)>0)//заменяем границы интервала

{

X1[0]=x;

Y1[0]=y;

}

else

{

X1[1] = x;

Y1[1] = y;

}

n++;

s=y;

}while(fabs(s)>0.000001);//задаем точность

cout << "x1="<< x << "" <<"n1=" << n <<endl;//выведем полученное решение и количество итераций

cout << "s=" << s << endl;

s=n=1;

getch();

return 0;

}

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

X[1]=2.0000000000

Y[1]=3.0000000000

x1=1.3221855164n1=19

s=0.0000005356

Решение уравнения найдено с точность до 0.000001. Погрешность вычислений составляет . Для достижения такой точности нам потребовалось сделать 19 итераций цикла.

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

Для нахождения корня мы берем функцию

Листинг 5. - программа на языке С++ для решения уравнения методом простых итераций.

#include<iostream.h>

#include<conio.h>

#include<math.h>

int main()

{

clrscr();

long double x, x1, y=1;

int n=1;

x=1;

do//цикл вычисления корня

{

x1=(pow(x,3)-3*x*x-5)/(-6);

x=x1;

y=(x*x*x-3*x*x+6*x-5);//проверка на равенство 0

n++;

}while(fabs(y)>0.000001);//задаем точность

cout << "x=" << x << "\ny=" << y << "n=" << n << endl;

getch();

return 0;

}

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

x=1.322185

y=-6.679253e-07n=19

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

Для достижения такой точности понадобилось сделать 19 итераций цикла. При подстановке данного значения в уравнение у получился равным нулю с точностью до 10-6.

Метод золотого сечения.

Для нахождения интервалов, в которых функция меняет знак, задаем цикл for, который проверяет значение функции на интервале от -100 до 100, с шагом 1.

Листинг 6. - Программа для решения уравнения методом золотого сечения.

//прога решает нелинейное уравнение методом золотого сечения.

#include<stdlib.h>

#include<iostream.h>

#include<conio.h>

#include<math.h>

int main()

{

clrscr();

double x,x1,x2,y,y1,y2,X[5],Y[5],s,t;

int n,i;

char l;

x=-100;

t=0.618;

y=pow(x,3)-3*pow(x,2)+6*x-5;

n=1;

cout.setf(ios::fixed);//флаг вывода чисел в формате с фиксированной запятой

cout.setf(ios::showpoint);

cout.precision(10);// вывод чисел с пятью знаками после запятой

for(x1=-100;x1<=100;x1++)//начинаем проверку графика на интервалы в которых функция имеет разные знаки с шагом 1

{

y1=pow(x1,3)-3*pow(x1,2)+6*x1-5;

if((y*y1)<0)

{

X[n]=x1;//если знак функции меняется, то записываем данную точку в массив

Y[n]=y1;

cout << "X[" << n << "]=" << X[n] << endl;

cout << "Y[" << n << "]=" << Y[n] << endl;

n++;

}

y=y1;

x=x1;

}

X[0]=(X[1]-1);//инициализируем первую точку

Y[0]=pow(X[0],3)-3*pow(X[0],2)+6*X[0]-5;

n=1;

double X1[]={X[0], X[1], X[1], X[2], X[2], X[3], X[3], X[4]};//инициализируем массив, удобный для работы

double Y1[]={Y[0], Y[1], Y[1], Y[2], Y[2], Y[3], Y[3], Y[4]};

do//цикл вычисления корня

{

x1=X1[0]+(1-t)*(X1[1]-X1[0]);

x2=X1[0]+t*(X1[1]-X1[0]);

y1=pow(x1,3)-3*pow(x1,2)+6*x1-5;

y2=pow(x2,3)-3*pow(x2,2)+6*x2-5;

if(fabs(y1)<fabs(y2))//заменяем границы интервала

{

X1[1]=x2;

}

else

{

X1[0] = x1;

}

n++;

s=fabs(x1-x2);

}while(fabs(s)>0.000001);//задаем точность

x=x1+t*(x2-x1);

y=pow(x,3)-3*x*x+6*x-5;

cout << "x1="<< x << "" <<"n1=" << n <<endl;//выведем полученное решение и количество итераций

cout << "y=" << y << endl;

getch();

return 0;

}

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

X[1]=2.0000000000

Y[1]=3.0000000000

x1=1.3221845946n1=28

y=-0.0000025167

Корень вычислялся с точностью до 0.000001. Абсолютная погрешность вычислений равна

Для достижения заданной точности понадобилось сделать 28 итераций цикла.

3.3 Решение уравнения

Построим график функции для определения количества корней уравнения.

Как видно из графика уравнение имеет один корень на промежутке [1;1.5].



Метод дихотомии.

Листинг 7. - Программа для решения уравнений методом дихотомии.

//прога решает нелинейное уравнение методом дихотомии

#include<stdlib.h>

#include<iostream.h>

#include<conio.h>

#include<math.h>

int main()

{

clrscr();

double x,x1,y,y1,X[5],Y[5],s;

int n,i;

char l;

x=-100;

y=pow(x,5)-3*pow(x,2)+x-1;

n=1;

cout.setf(ios::fixed);//флаг вывода чисел в формате с фиксированной запятой

cout.setf(ios::showpoint);

cout.precision(10);// вывод чисел с пятью знаками после запятой

for(x1=-100;x1<=100;x1++)//начинаем проверку графика на интервалы в которых функция имеет разные знаки с шагом 1

{

y1=pow(x1,5)-3*pow(x1,2)+x1-1;

if((y*y1)<0)

{

X[n]=x1;//если знак функции меняется, то записываем данную точку в массив

Y[n]=y1;

cout << "X[" << n << "]=" << X[n] << endl;

cout << "Y[" << n << "]=" << Y[n] << endl;

n++;

}

y=y1;

x=x1;

}

X[0]=(X[1]-1);//инициализируем первую точку

Y[0]=pow(X[0],5)-3*pow(X[0],2)+X[0]-1;

n=1;

double X1[]={X[0], X[1], X[1], X[2], X[2], X[3], X[3], X[4]};//инициализируем массив, удобный для работы

double Y1[]={Y[0], Y[1], Y[1], Y[2], Y[2], Y[3], Y[3], Y[4]};

do//цикл вычисления корня

{

x=(X1[0]+X1[1])/2;

y=pow(x,5)-3*pow(x,2)+x-1;

if((Y1[0]*y)>0)//заменяем границы интервала

{

X1[0]=x;

Y1[0]=y;

}

else

{

X1[1] = x;

Y1[1] = y;

}

n++;

s=y;

}while(fabs(s)>0.000001);//задаем точность

cout << "x1="<< x << "" <<"n1=" << n <<endl;//выведем полученное решение и количество итераций

cout << "s=" << s << endl;

getch();

return 0;

}

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

X[1]=2.0000000000

Y[1]=21.0000000000

x1=1.4084684849n1=23

s=0.0000005293

Программа нашла корень уравнения с точностью до 0.000001. Абсолютная погрешность вычислений . Для достижения такой точности понадобилось сделать 23 итерации цикла.

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

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

При попытке выразить х другим способом, ряд не сходится.

Листинг 8. - Программа для решения уравнения методом простых итераций.

#include<iostream.h>

#include<conio.h>

#include<math.h>

int main()

{

clrscr();

long double x, x1, y=1;

int n=1;

x=1;

do

{

x1=pow((3*x*x-x+1),(0.2));

x=x1;

y=(x*x*x*x*x-3*x*x+x-1);

n++;

}while(fabs(y)>0.000001);

cout << "x=" << x << "\ny=" << y << "n=" << n << endl;

getch();

return 0;

}

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

x=1.408468

y=-9.722666e-07n=17

В программе задавалась точность вычислений до 0.000001. Абсолютная погрешность равна . Для достижения заданной точности потребовалось сделать 17 итераций цикла.

Метод золотого сечения.

Листинг 9. - программа для нахождения корней уравнения методом золотого сечения.

//прога решает нелинейное уравнение методом золотого сечения

#include<stdlib.h>

#include<iostream.h>

#include<conio.h>

#include<math.h>

int main()

{

clrscr();

double x,x1,x2,y,y1,y2,X[5],Y[5],s,t;

int n,i;

char l;

t=0.618;

x=-100;

y=pow(x,5)-3*pow(x,2)+x-1;

n=1;

cout.setf(ios::fixed);//флаг вывода чисел в формате с фиксированной запятой

cout.setf(ios::showpoint);

cout.precision(10);// вывод чисел с пятью знаками после запятой

for(x1=-100;x1<=100;x1++)//начинаем проверку графика на интервалы в которых функция имеет разные знаки с шагом 1

{

y1=pow(x1,5)-3*pow(x1,2)+x1-1;

if((y*y1)<0)

{

X[n]=x1;//если знак функции меняется, то записываем данную точку в массив

Y[n]=y1;

cout << "X[" << n << "]=" << X[n] << endl;

cout << "Y[" << n << "]=" << Y[n] << endl;

n++;

}

y=y1;

x=x1;

}

X[0]=(X[1]-1);//инициализируем первую точку

Y[0]=pow(X[0],5)-3*pow(X[0],2)+X[0]-1;

n=1;

double X1[]={X[0], X[1], X[1], X[2], X[2], X[3], X[3], X[4]};//инициализируем массив, удобный для работы

double Y1[]={Y[0], Y[1], Y[1], Y[2], Y[2], Y[3], Y[3], Y[4]};

do//цикл вычисления корня

{

x1=X1[0]+(1-t)*(X1[1]-X1[0]);

x2=X1[0]+t*(X1[1]-X1[0]);

y1=pow(x1,5)-3*pow(x1,2)+x1-1;

y2=pow(x2,5)-3*pow(x2,2)+x2-1;

if(fabs(y1)<fabs(y2))//заменяем границы интервала

{

X1[1]=x2;

}

else

{

X1[0] = x1;

}

n++;

s=fabs(x1-x2);

}while(fabs(s)>0.000001);//задаем точность

x=x1+t*(x2-x1);

y=pow(x,5)-3*x*x+x-1;

cout << "x1="<< x << "" <<"n1=" << n <<endl;//выведем полученное решение и количество итераций

cout << "y=" << y << endl;

getch();

return 0;

}

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

X[1]=2.00

Y[1]=21.00

x1=1.4084677864n1=28

y=-0.0000080100

Точность результата, заданная в программе 0.000001. Абсолютная погрешность . Для достижения точности программа произвела 28 итераций цикла.

4. Анализ работы методов

Метод дихотомии требует менее всего итераций цикла для получения корней уравнения с заданной точностью. Если расчет ведется без помощи ЭВМ, то это значительный плюс в пользу этого метода. Для всех уравнений количество циклов, при решении данным методом примерно одинаково, в отличие от метода простых итераций. Для решения уравнения 2х+lg(x)+0.5=0 данным методом понадобилось сделать 36 итераций. Хотя для решения других уравнений понадобилось сделать 19 и 17 итераций. Отсюда можно сделать вывод, что метод простых итераций больше подходит для решения уравнений, которые представляют собой полиномы.

Сложность метода дихотомии, как и метода золотого сечения в нахождении интервалов перемены знака для заданной функции, что при подсчете вручную весьма трудоемко, тем более, если уравнение имеет больше одного корня. Эти два метода похожи друг на друга, отличаются только способы приближения к заданному значению <x> на отрезке [a;b].

Несмотря на внешнюю простоту метода простых итераций, основная сложность заключается в подборе функции для нахождения значений <x>. Во многих случаях ряд xi=G(xi-1) не сходится, и цикл уходит в бесконечность. Подобрать нужную функцию весьма трудоемко без применения ЭВМ.

Сравнивая результаты работы каждого метода, можно сказать следующее: универсальный и наименее трудоемкий - метод дихотомии. Он показал неплохие результаты для всех видов уравнений. Метод золотого сечения требует большого количества итераций, особенно при решении уравнений вида axn+bxn-1+…+jx+ix0=0. Метод итераций же наоборот больше подходит для решения таких уравнений.

Список использованной литературы

1. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы - М.: Лаборатория Базовых Знаний, 2000 г. - 624 с.: ил.

2. Демидович Б.П., Марон И.А. Основы вычислительной математики - М.: Наука, 1970 г. - 654 с.

3. Мэтьюс Джон Г., Финк Куртис Д. Численные методы. Использование MATHLAB, 3-е издание. пер. с англ. - М.: Издательский дом «Вильямс», 2001. - 720 с.

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