Наближене розв’язання нелінійного рівняння (метод дотичних)

ЄВРОПЕЙСЬКИЙ  УНІВЕРСИТЕТ 

ФІНАНСІВ, ІНФОРМАЦІЙНИХ  СИСТЕМ, МЕНЕДЖМЕНТУ І БІЗНЕСУ

 

 

Кафедра інформаційних  систем та технологій

 

 

 

 

 

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

на тему Наближене розв’язання нелінійного рівняння (метод дотичних)

           (назва  теми)

 

        з дисципліни  Основи програмування та алгоритмічні мови

( назва дисципліни)

 

 

Виконав: студентка 2 курсу, 206 група

факультету ІСТ Безнощенко Т.С.

                                                                                                      (прізвище, ініціали)

Керівник : к.т.н. Стешенко В.І.

(вч. ступінь, звання , прізвище, ініціали)   

 

 

 

Донецьк – 2005 р.

Содержание

 

 

1. Титульный лист ………………………………………….……………………. 1

2. Содержание ………………………………………….………………………… 2

3. Введение …………………………………………….…………………………. 3

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

    4.1. Обзор существующих  методов …………………….……….……………. 4

    4.2. Анализ метода  касательных (метода секущих Ньютона) …………….…6

    4.3. Решение  нелинейного уравнения аналитически ………………..………..7

5.Описание алгоритма решения задачи:

    5.1. Описание пользовательских  идентификаторов ……………..…………...11

    5.2. Блок-схема программы ………………………………………..…………...12

    5.3. Описание блок-схем ………………………………………..………..…….15

6. Тестирование программы на  контрольном примере ………………..…..........16

7. Сравнительный анализ данных  ручного просчета и 

     машинных экспериментов ……………………………………………..……....18

8. Описание программного обеспечения:

     8.1. Описание ОС …………………………………..…………………………...18

     8.2. Описание  среды программирования ……………..……………………….20

     8.3. Описание  программных модулей ………………..………………………..21

9. Вывод ……………………………………………………..……………………...22

10. Список литературы …………………………………..………………………...23

11. Приложение …………………………………………..………………………...24

 

 

 

 

 

 

 

 

3. Введение

 

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

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

Решение некоторых задач  непосредственно сводятся к нахождению корней трансцендентных уравнений. Например, простейшая цепь (рис.1) состоит из источника έ, нелинейного элемента (диод, транзистор и т.д.) RH и резистора нагрузки с сопротивлением R. Необходимо найти ток в цепи IA и напряжение на нелинейном элементе UА.

                 0

Е                       U                                   UA

 

                                                                         Рис.1

 

Напряжение и ток резистора рассчитывается согласно закону Ома для замкнутой цепи с помощью уравнения U=E-IR . Нелинейный элемент определяется вольтамперной характеристикой U=U(I). В результате для определения параметров IA  и UA получаем нелинейное уравнение относительно I: U(I)=E-IR.

Чтобы решить нелинейное уравнение f(x)=0, где f(x) – алгебраическая или трансцендентная функция, определенная и непрерывная на конечном или бесконечном интервале a<x<b, необходимо пройти 2 этапа:

 

1-й этап: выделение  корней, то есть нахождение промежутков, в которых содержится только один корень уравнения;

2-й этап: уточнение  приближенных корней, то есть  получение значений корня с  заданной точностью.

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

 

4.1.Обзор существующих  методов

 

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

1. Метод хорд. Заменим на отрезке [a,b] кривую y=f(x) хордой, которая соединяет точки А и В (рис.1.). За приближенное значение корня выберем точку пересечения хорды с осью ох. Значение функции f(x1) сравниваем со значениями f(a) и f(b). В дальнейшем рассматриваем отрезок [a1,b1]=[a1,x1],  если f(a)f(x1)<0, и отрезок [a1,b1]=[x1,b]  в противном случае. Для нахождения приближенного значения корня имеем формулу:

xn+1=xn+c-xn/1-f(c)/f(xn)

 

где xn+c-xn – числитель,

1-f(c)/f(xn) – знаменатель,

С – неподвижный конец  отрезка [a,b].

За неподвижный конец  следует выбирать точку с=а, если f(a)f”(a)>0, и точку с=b, если f(b)f”(b)>0.

   В случае, когда  имеет место неравенство М≤2m1, где

 

 m1=min|f’(x)|, M1=max|f’(x)|

       [a,b] [a,b]

 

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

|x*-x|<|xn+1-xn|<ε

 

(Рис.1)

 

    Недостаток этого метода в неточности вычислений.

2. Метод итераций. При решении нелинейного уравнения методом итераций пользуются записью уравнения в виде x=f(x). (Уравнение f(x)=0 заменили равнозначным). Задаются начальное значение аргумента x₀ и точность ε. Первое приближение решения x₁ находим из выражения x₁=f(x₀), второе - x₂=f(x₁) и т.д. В общем случае i+1 приближение найдем по формуле x_i+1 =f(x_i). Указанную процедуру повторяем пока |f(x_i)|>ε. Условие сходимости метода итераций |f'(x)|<1.

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

3. Метод половинного  деления. При решении нелинейного  уравнения методом половинного деления задаются интервал [a,b], на котором существует только одно решение, и желаемая точность ε. Затем определяется середина интервала с=(а+b)/2 и проверяется условие F(a)∙F(c)<0. Если указанное условие выполняется, то правую границу интервала b переносим в среднюю точку с (b=c). Если условие не выполняется, то в среднюю точку переносим левую границу(a=c). Деление отрезка пополам продолжается пока |b-a|>ε.

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

 

4.2. Анализ метода касательных  (метод секущих Ньютона)

 

В основу метода касательных  лежит идея линеаризации. Но в этом случае, кривая y=f(x) последовательно замещается касательными, для которых находится точка пересечения с осью ox (рис.2) (в случае действительных корней). Формула для последовательных приближений к корню:

xn+1=xn-f(xn)/f’(xn)

Причем, x0=a, если f(a)f”(a)>0,  и x0=b, если f(b)f”(b)>0.

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

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

 

|xn+1-xn|<√2m1ε/M2, где M2=max|f”(x)|

                                                 [a,b]

 

(Рис.2)

 

4.3.Решение нелинейного  уравнения аналитически.

 

Метод Ньютона рассмотрен на нижеприведенном уравнении:

x¹-x³-2x²+3x-3=0

1-й этап: нахождение  промежутков, в которых находится корень уравнения.

f(x)= x¹-x³-2x²+3x-3

Область допустимых значений функции f(x) вся числовая ось:

xє]-∞,∞[.

Найдем f’(x):  f’(x)=4x³-3x²-4x+3

Найдем корни производной: 4x³-3x²-4x+3=0

                                                4x(x²-1)-3(x²-1)=0

                                                 (x²-1)(4x-3)=0

                                                  x1=-1;

                                                  x2=1;

                                                  x3=3/4.

Составим таблицу значений функции f(x):

x	-∞	-1	3/4	1	+∞
Sign f(x)	+	-	-	-	+

 

То есть, уравнение  имеет 2 действительных корня, которые  находятся на промежутках: x1є]-∞,-1[ и x2є]1,∞[.

Уменьшим промежутки, которые имеют корни таким  образом, чтоб их длина была не больше единицы:

 

x	-2	-1	1	2
Sign f(x)	+	-	-	+

 

Отсюда видно, что x1є]-2,-1[ ;  x2є]1,2[.

 

2-й этап: уточнение корней при  помощи метода Ньютона.

Рассмотрим промежуток [-2;-1], где  находится первый корень x1.

    f’=4x³-3x²-4x+3

     f”=12x²-6x-4

f1(a)*F2(a)=392 >0

 

Заметка: под f1(a) подразумевается 1-я производная, а        под F2(a) подразумевается 2-я производная.

 

f’=4x³-3x²-4x+3

   m1=min|y’(x)|

           [-2;-1]

 

12x²-6x-4=0

6x²-3x-2=0

    D=b²-4ac

D=9+48=57

    x1,2=-b±√D/2a

x1,2=3±√57/12

x1=0,87 – не принадлежит отрезку [-2;-1]

x2=-0,38

 

|f’(-2)|=|-33|                                   

f’(-0,38)=3,87

f’(-1)=0                          m1(min)=0

f”’=24x-6                                  

f”(-2)=56

f”(-1)=14                        M2(max)=56

 

Ниже данные сгруппированы  в таблицу:

 

f1(x)	f2(x)	f(a)*F2(a)	a	b	eps
-33	56	392	-2	-1	1E-10

 

Расчеты и график функции, сделанные в Excel:

 

xn	f(xn)	f1(xn)	f2(xn)	Xn1	Xn1-xn	Корень(2*m1*Eps/M2)
-2	7	-33	56	-1,78788	0,212121	3,71772E-06
-1,78788	1,1760227	-22,297965	45,08546	-1,73514	0,052741
-1,73514	0,0615176	-19,987538	42,53931	-1,73206	0,003078
-1,73206	0,0002013	-19,856836	42,39279	-1,73205	1,01E-05
-1,73205	2,177E-09	-19,856406	42,3923	-1,73205	1,1E-10
-1,73205	-3,55E-15	-19,856406	42,3923	-1,73205	0

 

 

 

Как видно из расчетов таблицы, первый корень рамен: -1,73205.

Рассмотрим промежуток [1;2], где  находится второй корень x2.

f’=4x³-3x²-4x+3

f”=12x²-6x-4

(f’и f”такие же как и для первого корня)

                              Теперь ищем m1 и M2:

|f’(1)|=|0|

|f’(2)|=|15|                       m1(min)=0

|f”(1)|=|2|

|f”(2)|=|32|                      M2(max)=32

 

Ниже данные сгруппированы  в таблицу:

 

f1(x)	f2(x)	f(a)*F2(a)	a	b	eps
0	32	-64	1	2	1E-10