«Методы решения нелинейных уравнений». КУРСОВАЯ РАБОТА по дисциплине «Информатика и программирование».

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Международная «Лига развития науки и образования» (Россия)

Международная ассоциация развития науки, образования и культуры России

(Италия)

Международный «ИНСТИТУТ УПРАВЛЕНИЯ»

(г. Архангельск)

КУРСОВАЯ РАБОТА

ПО ДИСЦИПЛИНЕ

«Информатика и программирование»

по теме: «Методы решения нелинейных уравнений»

+-----------------------------+

| Выполнил: студент |

| экономического факультета, |

| группы 14-И Дроздов А.Ю. |

| |

| Проверил: Горяшин Ю.В. |

+-----------------------------+

Архангельск

2005

Аннотация

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

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

в заданной точке, а также вычисления значения нелинейного уравнения

методом секущих написанных на языке программирования Turbo С 2.0.

Содержание

Введение 4

1. Метод решения нелинейного уравнения методом секущих 7

1.1. Общая характеристика методов решения нелинейных уравнений 7

1.2. Метод секущих 10

1.3. Тестовый пример 12

1.4. Разработка алгоритма решения нелинейных уравнений 15

2. Вычисление значения функции при помощи интерполяционной формулы 16

2.1. Общая характеристика методов интерполяционной функции 16

2.2. Интерполяционная формула Ньютона 24

2.3. Тестовый пример 25

2.4. Разработка алгоритма и программы вычисления функции 26

Заключение 27

Список литературы 28

Приложение 1.1 29

Приложение 2.1 31

Введение

Целью курсовой работы является разработка программы решения нелинейных и

трансцендентных уравнений методом секущих - хорд. Программа включает и

учитывает многие новые возможности в программировании и практике создания

программ в среде программирования С.

Процедура подготовки и решения задачи на ЭВМ достаточно сложный и

трудоемкий процесс, состоящий из следующих этапов:

1. Численные методы линейной алгебры

Метод Гаусса для решения системы линейных алгебраических уравнений.

Устойчивость метода Гаусса. Использование метода Гаусса для вычисление

обратной матрицы. Метод квадратного корня.

Решение систем линейных алгебраических уравнений с ленточными матрицами.

Пример решения линейной системы с трехдиагональной матрицей.

Одношаговые итерационные методы решения систем линейных алгебраических

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

методов. Достаточное условие сходимости.

Необходимое и достаточное условие сходимости одношаговых стационарных

итерационных методов. Теорема о сходимости одношаговых стационарных

итерационных методов. Оценка скорости сходимости. Неявный итерационный

метод с чебышевским набором параметров. Оценка скорости сходимости.

Численная устойчивость итерационного метода с чебышевским набором

параметров. Упорядоченный набор итерационных параметров (пример).

Одношаговые итерационные методы вариационного типа. Формула для вычисления

итерационного параметра.

Примеры итерационных методов вариационного типа (метод скорейшего спуска;

метол минимальных невязок; метод минимальных поправок; метод минимальных

погрешностей) . Каноническая форма записи двухшаговых итерационных методов

вариационного типа.

Примеры двухшаговых итерационных методов (метод сопряженных градиентов,

сопряженных невязок, сопряженных поправок, сопряженных погрешностей).

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

Степенной метод решения частичной проблемы собственных значений. Решение

полной проблемы собственных значений методом вращений. Метод обратной

итерации.

2. Решение нелинейных уравнений и систем уравнений.

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

методов решения нелинейных уравнений (метод простой итерации, метод

Ньютона, модифицированный метод Ньютона, метод секущих).

Сходимость метода простой итерации.

Метод Эйткена ускорения сходимости.

Сходимость метода Ньютона.

Решение систем нелинейных уравнений.

Примеры (применение метода простой итерации; сравнение скорости сходимости

метода простой итерации и метода Ньютона; применение метода Ньютона для

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

3. Интерполяция и приближение функций.

Постановка задачи интерполирования алгебраическими многочленами.

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

(разделенные разности, схема Горнера).

Интерполирование с кратными узлами (существование и единственность

многочлена Эрмита, погрешность интерполирования с кратными узлами). Пример

(многочлен Эрмита третьей степени). Сходимость интерполяционного процесса.

Интерполирование сплайнами. Кубический сплайн. Наилучшее приближение

функции, заданной таблично (пример). Наилучшее приближение в гильбертовом

пространстве.

Глава 1. Метод решения нелинейного уравнения методом секущих

1.1. Общая характеристика методов

1. Условие задания

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

вычислить приближенное значение корня функционального уравнения вида f (x)

= 0, если известно, что это уравнение имеет единственный корень на отрезке

[a, b].

В проекте должно быть предусмотрено:

- построение графика функции f (x) на отрезке [a, b],

- проверка корректности введенных значений исходных данных (выполнение

условия a < b, выполнение условия e > 0),

- перехват и обработка ошибки времени выполнения, когда строку введенных

символов невозможно интерпретировать как число.

2. Содержание пояснительной записки

Пояснительная записка должна иметь титульный лист, оглавление, нумерацию

страниц, а также включать:

0x01 graphic

условие задачи;

0x01 graphic

условия заданного варианта задания;

0x01 graphic

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

0x01 graphic

блок-схему алгоритма подзадачи вычисления корня;

0x01 graphic

программу процедуры вычисления корня;

0x01 graphic

главную программу;

0x01 graphic

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

допустимой ошибки

Варианты численного метода:

1) метод простых итераций,

2) метод Ньютона,

3) метод проб,

4) метод секущих,

5) метод хорд.

Упрощенный метод Ньютона: 0x01 graphic

, n=0,1,…

Метод ложного положения: 0x01 graphic

, n=0,1,…;

c - фиксированная точка из окрестности корня

Метод секущих: 0x01 graphic

, n=0,1,…

Метод Стеффенсена: 0x01 graphic

, n=0,1,…

3. Описание Метод секущих

Метод секущих, так же, как и метод проб, использует не одно, а два

начальных приближения, которые мы обозначим соответственно x[n1] и x[n2].

Перед выполнением первой итерации воспользуемся правилом (6) для

определения значений этих приближений.

При выполнении каждой очередной итерации для вычисления следующего

приближения по методу хорд проведем прямую линию (секущую) MN через точки

с координатами (x[n1], f(x[n1])) и (x[n2], f (x[n2])), а абсциссу точки

пересечения секущей MN с осью х возьмем в качестве значения следующего

приближения x[s] к корню (рис. 3).

+------------------------------------------------------------------+

| 0x08 graphic |

| 0x01 graphic |

|------------------------------------------------------------------|

| Рис. 3. Графическая иллюстрация метода секущих |

+------------------------------------------------------------------+

Принятое правило нахождения следующего приближения приводит к расчетной

формуле:

Из трех приближений к корню оставим два последних (отбрасываем самое

старое x[n1]). В методе секущих это делается по следующему правилу:

x[n1] = x[n2]; x[n2] = x[s].

Выполнение итераций можно прекратить при выполнении условия

|x[n2] - x[n1]|< e,

а полученное значение приближения x[s] взять в качестве искомого значения

корня x[w].

Расчетные формулы должны быть применены в алгоритме вычисления корня по

методу секущих.

Обратим внимание на то, что формула имеет много общего с формулой Ньютона.

Знаменатель в формуле есть не что иное, как среднее значение производной

f^`(x) на отрезке [x[n1], x[n2]].

1.2. Метод секущих

Пусть на отрезке [a; b] отделен корень с уравнения f(x) = 0 и f-функция

непрерывна на отрезке [a; b], а на интервале ]a; b[ существуют отличные от

нуля производные f \' и f ”.

Так как f \'(x) ** 0 , то запишем уравнение f(x) = 0 в виде :

x = x - ( f(x)/f \'(x)) (1)

Решая его методом итераций можем записать :

xn+1 = x n- ( f(x n)/f \'(x n)) (2)

Если на отрезке [a;b] f \'(x) * f “(x) > 0, то нул - евое приближение

выбираем x0=a. Рассмотрим геометрический смысл метода . Рассмотрим график

функции y=f(x). Пусть для определенности f `(x) > 0 и f “(x) > 0 (рис. 1).

Проведем касательную к графику функции в точке B(b,f(b)). Ее уравнение

будет иметь вид:

y = f(b) + f \'(b) * (x -b)

Полагая в уравнении y = 0 и учитывая что f \'(x) ** 0, решаем его

относительно x. Получим :

x = b - (f (b) /f `(b))

Нашли абсциссу x1 точки c1 пересечения касательной с осью ox :

x1 = b - (f (b) - f \' (b))

Проведем касательную к графику функции в точке b1 (x1; f (x1)).Найдем

абсциссу x2 точки с2 пересечения касательной с осью Ox :

x2 = x1 - (f (x1)/( f \'(x1))

Вообще :

xk+1=x k - (f(x k)/f \'(x k)) (3)

Таким образом, формула (3) дает последовательные приближения (xk) корня,

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

точке b k(x k;f(x k0) метод уточнения корня c [a;b] уравнения f(x) = 0 с

помощью формулы (3) называется методом касательной или методом Ньютона.

Геометрический смысл метода касательных состоит в замене дуги y = f (x)

касательной, одной к одной из крайних точек . Начальное приближение x0 = a

или x0 = b брать таким, чтобы вся последовательность приближения х k

принадлежала интервалу ]a;b[ . В случае существования производных f \', f

”, сохраняющих свои знаки в интервале, за х0 берется тот конец отрезка

[a;b], для которого выполняется условие f \'(х0) * f (х0) > 0. Для оценки

приближения используется общая формула :

|c-x k-1 | ** | f (x k+1)/m| , где m = minf\'(x) на отрезке [a;b] .

На практике проще пользоваться другим правилом :

Если на отрезке [a;b] выполняется условие 0 < m < | f (x)| и ** **

заданная точность решения, то неравенство | x k+1-x k| ** ** влечет

выполнение неравенства |c-x k-1| ** ** **

В этом случае процесс последовательного приближения продолжают до тех пор,

пока не выполнится неравенство :|c-x k-1| ** ** **

Упрощенный метод Ньютона: 0x01 graphic

, n=0,1,…

Метод секущих: 0x01 graphic

, n=0,1,…

1.3. Тестовый пример

Для заданного нелинейного уравнения вида f(x)=0 графическим или

аналитическим способом найти интервалы локализации корней, 5^x-3x-5=0

1. 5^x-3x-5=0; y=5^x y=3x-5

5^x=3x+5 x -2 -1 0 1 2 x -2 2

y 0,04 0,2 1 5 25 y -1 11

a. графический метод

Первое решение находится в интервале (-2;-1). Второе в интервале (1;2)

0x08 graphic

0x01 graphic

б) метод секущих

1) (-2;-1)

f(x)=5^x-3x-5

f(-2)=5^-2+6-5=1/25+1=26/25=1.04>0

f(-1)=5^-1+3-5=1/5-2=-1.80

x[1]=a-(b-a)f(a)/f(b)-f(a)=1-(2-1)*(-3)/-14+3=1+3/17=1.1765

f(1.1765)=5^1.1765+3*1.1765-5=-1.8869

#include

double f(double x)

{

return 5^x-3*x-5;

}

double findRootChord (double a,

double b,

double eps,

long max_step,

double (&f)(double))

{

double f_a = f(a);

double f_b = f(b);

double xn;

for(long k=0; k

#include

float FileFunction()

{ float h;

FILE *in;

in=fopen(\"spisok.txt\",\"r\");

for (;!feof(in);)

{

w_f=(struct files *)malloc(sizeof(struct files));

if(l_f==NULL) {l_f=w_f;}

else {r_f->radr=w_f;}

fscanf(in,\"%f\",&w_f->x);

fscanf(in,\"%f\",&w_f->y);

r_f=w_f;

}w_f=l_f;

fclose(in);

w_f=l_f->radr;

h=(w_f->x)-(l_f->x);

return h;

}

void TableMin()

{

float s,s1,p;

{

s=w_f->y;

w_f=w_f->radr;

s1=w_f->y;

p=s1-s;

w_msp=(struct msp *)malloc(sizeof(struct msp));

w_fll=(struct fll *)malloc(sizeof(struct fll));

if(l_msp==NULL){l_msp=w_msp;}

else{r_msp->radr1=w_msp;}

if(l_fll==NULL){l_fll=w_fll;}

else{r_fll->radr2=w_fll;}

w_fll->a=p;r_fll=w_fll;

w_msp->z=p;r_msp=w_msp;

}

while(w_f!=r_f);

w_msp=l_msp;

return;

}

void TableMax()

{

float p,s,s1,i,c;

for(i=1;iz;

l_msp=NULL;

{

s=c;

w_msp=w_msp->radr1;

c=w_msp->z;

s1=w_msp->z;

p=s1-s;

w_fll=(struct fll *)malloc(sizeof(struct fll));

r_fll->radr2=w_fll;

w_fll->a=p;r_fll=w_fll;

r_msp->radr1=w_msp;

if(l_msp==NULL){w_msp->z=p;l_msp=w_msp;}

else{w_msp->z=p;}

}while(w_msp!=r_msp);

r_msp=w_msp;

w_msp=l_msp;

}

return;

}

float UX(float x,float h)

{

float u,u1;

int i=1;

w_f=l_f;

while(w_f!=r_f){w_f=w_f->radr;i++;}

i=(i/2);

for(w_f=l_f;i>=1;i--){w_f=w_f->radr;}

u=(x-(w_f->x))/h;

w_u=(struct u *)malloc(sizeof(struct u));

l_u=w_u;

w_u->u=u;

r_u=w_u;

for(i=1;iu);

w_u=(struct u *)malloc(sizeof(struct u));

r_u->uadr=w_u;

w_u->u=u1;

r_u=w_u;

}

return u;

}

float VX(float u)

{

float v1,v,i;

v=1-u;

w_v=(struct v *)malloc(sizeof(struct v));

l_v=w_v;

r_v->vadr=w_v;

w_v->v=v;

r_v=w_v;

for(i=1;iv);

w_v=(struct v *)malloc(sizeof(struct v));

r_v->vadr=w_v;

w_v->v=v1;

r_v=w_v;

}

return 1;

}

float Summa()

{

int j,i=1;

float s,s1,p;

w_f=l_f;

w_fll=l_fll;

w_u=l_u;

w_v=l_v;

while(w_f!=r_f){w_f=w_f->radr;i++;}

i=(i/2);

for(w_f=l_f;i>=1;i--){w_f=w_f->radr;}

s=(w_f->y)*(w_v->v);

w_f=w_f->radr;

s1=(w_f->y)*(w_u->u);

w_f=l_f;

while(w_f!=r_f){w_f=w_f->radr;i++;}

i++;

j=i;

{

if(i==0){j--;}

i=j;

j=i-1;

i=j;

for(;i>=1;i--){w_fll=w_fll->radr2;}

i=j;

for(i=((i/2)-1);i>=1;i--){w_fll=w_fll->radr2;}

w_v=w_v->vadr;

s=s+(w_fll->a)*(w_v->v);

i=j;

for(i=((i/2));i>=1;i--){w_fll=w_fll->radr2;}

}while(w_fll!=r_fll);

w_fll=l_fll;

w_f=l_f;

while(w_f!=r_f){w_f=w_f->radr;i++;}

j=i;

w_u=l_u;

{

j=i;

for(;i>=1;i--){w_fll=w_fll->radr2;}

i=j-1;

for(i=((i/2)+1);i>=1;i--){w_fll=w_fll->radr2;}

w_u=w_u->uadr;

s1=s1+(w_fll->a)*(w_u->u);

i=j-1;

j=0;

i=i-1;

for(i=((i/2));i>=1;i--,j++){w_fll=w_fll->radr2;}

i=j*2;

}while(w_u!=r_u);

p=s1+s;

return p;

}

void main()

{

float p,u,h,x;

l_msp=NULL;l_fll=NULL;l_f=NULL;

w_u=NULL;r_u=NULL;l_u=NULL;

w_v=NULL;r_v=NULL;l_v=NULL;

h=FileFunction();

w_f=l_f;

TableMin();

TableMax();

printf(\"\\n BBEDuTE X=\");

scanf(\" %f\",&x);

u=UX(x,h);

VX(u);

p=Summa();

printf(\"\\nOTBET: %3.4f\",p);

getch();

}

0x08 graphic

0x01 graphic

+----+

|x* |

+----+

+-----+

|]x[s |

+-----+

+-------+

|]x[n2 |

+-------+

|]x[n1 |

+-------+

+----+

|N |

+----+

+---+

|М |

+---+

|x |

+---+

|y |

+---+

+------+

|y = |

|f(x) |

+------+

+---+

|b |

+---+

|a |

+---+

-2

-1

y=5^x

y=3x-5

Конец

«OTBET: »

p=Summa();

VX(u);

u=UX(x,h);

BBEDuTE X=

TableMax();

TableMin();

w_f=l_f;

h=FileFunction();

l_msp=NULL;l_fll=NULL;l_f=NULL;

w_u=NULL;r_u=NULL;l_u=NULL;

w_v=NULL;r_v=NULL;l_v=NULL;

Начало

Конец

Вывод значения x на печать

Abs(b-x) меньше заданной точности

Расчет следующего значения X= x по формуле:

x=a-f(a)*(b-a)/(f(b)-f(a))

Процедура для расчета значения заданной функции Y = y при значении X = x

Расчёт значения Y = c при некотором значении X = a

Сохранение предыдущего значения x в переменной b

Выбор значения Х = x