Приблизительное решение нелинейного уравнения (метод касательных)

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

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

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

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

на тему

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

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

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

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

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

Донецьк - 2005 р.

Содержание

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

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

3. Введение

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

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

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

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

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

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

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

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

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

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

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

8.1 Описание ОС

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

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

Вывод

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

Приложение

3. Введение

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

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

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

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

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

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

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

Рис.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 заменили равнозначным). Задаются начальное значение аргумента x0 и точность е. Первое приближение решения x1 находим из выражения x1=f(x0), второе - x2=f(x1) и т.д. В общем случае i+1 приближение найдем по формуле xi+1 =f(xi). Указанную процедуру повторяем пока |f(xi)|>е. Условие сходимости метода итераций |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|<v2m1е/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±vD/2a

x1,2=3±v57/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

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

xn	f(xn)	f1(xn)	f2(xn)	Xn1	Xn1-xn	корень(2*m1*Eps/M2)
2	3	15	32	1,8	-0,2	0
1,8	0,5856	9,408	24,08	1,737755102	-0,062244898
1,737755	0,045167903	7,980242552	21,81098292	1,732095136	-0,005659966
1,732095	0,000348282	7,857364326	21,6092719	1,73205081	-4,43255E-05
1,732051	2,12279E-08	7,856406519	21,60769525	1,732050808	-2,70199E-09
1,732051	0	7,856406461	21,60769515	1,732050808	0

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

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

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

a - константа, типа real (вещественный тип), размер: 8 байт, в 1 случае равная -2, во 2 случае 1; обозначает край промежутка, на котором находится корень уравнения.

b - константа, типа real (вещественный тип), размер: 8 байт, в 1 случае равная -1, во 2 случае 2; обозначает край промежутка, на котором находится корень уравнения.

Eps - константа, равная 0,0000000001, типа real (вещественный тип), размер 8 байт; обозначает погрешность.

m1 - константа, типа integer (целого типа), размер 4 байта, в 1 случае равная 0 и во 2 случае также равна 0. Обозначает минимальное значение (по модулю) производной значения точки (-1) в первом случае и точки (1) во втором случае.

M2 - константа, типа integer (целого типа), размер 4 байта, в 1 случае равная 56,во 2 случае равна 32. Обозначает максимальное значение (по модулю) производной значения точки (-2) в первом случае и точки (2) во втором случае.

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

xn - переменная, вещественный тип, размер 8 байт, участвует в формулах по присвоению и вычислению значений.

xn1 - переменная, вещественный тип, размер 8 байт, участвует в формулах по присвоению и вычислению значений.

f - локальная переменная, вещественного типа, размер 8 байт, это функция,которая вычисляется по формуле.

f1 - (также как и f) но явл.производной функции.

f2 - (также как f1) но в отличии от f1 является второй прозводной.

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

Основная блок-схема

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

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

Вспомогательные блок-схемы

Для f

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

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

Для f1-для нахождения приближений

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

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

Для f2-для нахождения края, с которого начинаются итерации

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

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

5.3 Описание блок-схем программы

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

Блок-схема №1

1. Блок начала программы.

2. Блок объявления констант.

3. Блок объявления переменных.

4. Проверка условия.

5. Присвоение переменной значения в случае выполнения условия.

6. Присвоение переменной значения в случае не выполнения условия.

7. Расчет начального приближенного значения.

8. Проверка следующего условия (начало цикла). В случае не выполнения, переходим к блоку 8. В случае выполнения, в цикл не заходим и сразу осуществляем переход к 10 блоку.

9. Расчет приближенного значения.

10. Вывод промежуточных результатов.

11. Вывод окончательных результатов.

12. Блок окончания программы.

Блок-схема №2

1. Блок начала программы.

2. Ввод аргумента

3. Расчет функции по формуле.

4. Вывод результата f(x)

5. Блок окончания программы.

Блок-схема №3

1. Блок начала программы.

2. Ввод аргумента

3. Расчет функции по формуле.

4. Вывод результата f1(x)

5. Блок окончания программы.

Блок-схема №4

1. Блок начала программы.

2. Ввод аргумента

3. Расчет функции по формуле.

4. Вывод результата f2(x)

5. Блок окончания программы.

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

Программа была тестирована на следующем примере: x?-x?-2x?+3x-3=0.

Результаты выполнения расчетов программой, написанной на языке программирования Turbo Pascal приведены ниже.

Правильность метода была проанализирована ручным расчетом.

Ot A=-2.0000 do B=-1.0000

Pogrewnost E 0.0000000001

xn= -1.7878787879 xn+1= -1.7351386122 f(xn+1)= 0.0615150328

xn= -1.7351386122 xn+1= -1.7320609420 f(xn+1)= 0.0002012359

xn= -1.7320609420 xn+1= -1.7320508077 f(xn+1)= 0.0000000022

xn= -1.7320508077 xn+1= -1.7320508076 f(xn+1)= 0.0000000000

xn= -1.7320508076 xn+1= -1.7320508076 f(xn+1)= 0.0000000000

Kon.znach

xn1= -1.7320508076f(xn1)= 0.0000000000

Vtoroy koren

Ot A= 1.0000 do B= 2.0000

Pogrewnost E 0.0000000001

xn= 1.8000000000 xn+1= 1.7377551020 f(xn+1)= 0.0451679035

xn= 1.7377551020 xn+1= 1.7320951358 f(xn+1)= 0.0003482818

xn= 1.7320951358 xn+1= 1.7320508103 f(xn+1)= 0.0000000212

xn= 1.7320508103 xn+1= 1.7320508076 f(xn+1)= 0.0000000000

xn= 1.7320508076 xn+1= 1.7320508076 f(xn+1)= 0.0000000000

Kon.znach

xn1= 1.7320508076f(xn1)= 0.0000000000

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

Первый корень	Второй корень
Excel	Pascal	Excel	Pascal
-1,78788	-1.7878787879	1,8	1.8000000000
-1,73514	-1.7351386122	1,737755102	1.7377551020
-1,73206	-1.7320609420	1,732095136	1.7320951358
-1,73205	-1.7320508077	1,73205081	1.7320508103
-1,73205	-1.7320508076	1,732050808	1.7320508076
-1,73205	-1.7320508076	1,732050808	1.7320508076

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

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

8.1 Описание ОС Windows

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

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

Совместимость между интерфейсами различных прикладных программ достигается в Windows благодаря 32-разрядному интерфейсу API (Application Program Interface - интерфейс прикладных программ), предоставляющему программистам полный набор функций и ресурсов для создания средств интерфейса, с помощью которого приложения могут управлять файлами или отображением информации на экране дисплея.

Одной из важнейших возможностей Windows является поддержка технологии самонастраивающихся устройств Plug and Play. Их назначение - распознавание операционной системой любых периферийных устройств и управление ими.

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

Архитектура Windows построена на системе представлений об управлении виртуальной машиной в защищенном режиме работы процессора. Черты Windows:

Мультизадачный режим работы.

Оптимальное управление ресурсами компьютера.

Графический пользовательский интерфейс.

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

Возможность работы в сетевой среде.

Интерфейс мультимедиа.

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

Алгоритмический язык Паскаль разработан профессором Цюрихского технологического института Никлаусом Виртом в 1969-71 гг для обучения студентов структурному программированию. Идеи, заложенные в основу создания языка, позволили фирме Borland International значительно расширить алгоритмические средства языка, а удобное меню команд и высокая скорость компиляции сделали язык Турбо Паскаль одним из самых распространенных среди начинающих программистов.

Процесс программирования начинается, как правило, с составления алгоритма - последовательности операций, описывающих процесс решения задачи. Программирование заключается в записи алгоритма на языке программирования и отладки программы. Текст программы записывается в текстовом редакторе, затем программа компилируется - переводится транслятором (переводчиком) в машинные коды и запускается на выполнение. Процесс отладки программы начинается с выявления:

1.Синтаксических ошибок в тексе;

2.Ошибок при выполнении программы (недопустимые математические действия, операции с числами, превосходящими определенные значения);

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

Для загрузки среды Турбо-Паскаль запускается файл turbo.exe, расположенный в папке BIN.

Положительные черты:

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

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

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

Оптимизирующие средства трансляторов с паскаля позволяют создавать эффективные программы. Это послужило одной из причин использования паскаля в качестве языка системного программирования.

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

В минимальной конфигурации не требует инсталляции.

Процедурный язык.

Недостатки:

Работает под DOS.

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

Малое количество графических команд.

Невозможность работы с хорошим расширением.

Отсутствие функции возведения в степень.

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

Файл носит название: metod_kasatelnuh;

расширение: pas;

размер: 1,5 байт;

устанавливается: запуском из среды Turbo Pascal;

запуск: 1) Run-Run;

2)Ctrl + F9;

3)После компиляции программы на Паскале (Run-Run)

создается выполняемый exe - файл. Его можно запустить в

Windows двоичным щелчком.

Вывод

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

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

Алгоритм решения задачи достаточно прост и его удобно представить в блок-схемах, на основе которых и составлялась в дальнейшем программа. Объем программы невелик, поэтому в качестве носителя могла использоваться дискета.

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

1. Алексеев В.Е., Ваулин А.С., Петрова Г.Б. - Вычислительная техника и программирование. Практикум по программированию: Практ.пособие/-М.: Высш.шк., 1991.-400с.

2. Вычислительная техника и программирование: Учебник для техн. вузов/ Петров А.В., Алексеев В.Е., Ваулин А.С. и др.-М.: Высш.шк., 1990-479 с.

3. Гусев В.А., Мордкович А.Г. - Математика: Справ. материалы: кн.для учащихся-2-е изд.М.:Просвещение, 1990.-416 с.

4. Методичні указання (ДонНУ), с.25-30

5. А.Гарнаев «Exel, VBA, Internet в экономике и финансах»: Санкт-Перергург,2001 г.

6. «Введение в С++» Бьярн Страуструп (электронная версия).

7. «Учимся программировать на Pascal»,Ален Голуб,учебник.

8. «Turbo Pascal» Валерий Фаронов, Санкт-Петербург,2003.

9. «Алгоритмические трюки для программистов», Генри С. Уоррен младший (электронная версия).

10. «Использование шаблонов в Pascal» статья на сайте Гречина А.А. 2005 г.

Приложение

(Листинги программы)

program metod;

uses crt;

var xn,xn1,a,b,eps:real;

m1,m2:integer;

function f(x:real):real

begin

f:=x*x*x*x-x*x*x-2*x*x+3*x-3;

end;

function f1(x:real):real

begin

f1:=4*x*x*x-3*x*x-4*x+3;

end;

function f2(x:real):real;

begin

f2:=12*x*x-6*x-4;

end;

begin

clrscr;

a:=-2;b:=-1;eps:=0.0000000001;m1:=0;

m2:=56;

writeln('Ot A=',a,' do B=',b);

writeln('Pogrewnost E ',eps:15:10);

readln;

if f(a)*f2(a)>0

then xn:=a

else xn:=b;

xn1:=xn-f(xn)/f1(xn);

while abs(xn1-xn)>sqrt(2*m1*eps)/M2 do

begin

xn:=xn1;

xn1:=xn-f(xn)/f1(xn);

writeln('xn=',xn:15:10,' xn+1=',xn1:15:10,' f(xn+1)=',f(xn1):15:10);

readln;

end;

writeln('Kon.znach');

writeln('xn1=',xn1:15:10,'f(xn1)=',f(xn1):15:10);

readln;

writeln('Vtoroy koren');

a:=1;b:=2;eps:=0.0000000001;m1:=0;

m2:=32;

writeln('Ot A=',a,' do B=',b);

writeln('Pogrewnost E ',eps:15:10);

readln;

if f(a)*f2(a)>0

then xn:=a

else xn:=b;

xn1:=xn-f(xn)/f1(xn);

while abs(xn1-xn)>sqrt(2*m1*eps)/M2 do

begin

xn:=xn1;

xn1:=xn-f(xn)/f1(xn);

writeln('xn=',xn:15:10,' xn+1=',xn1:15:10,' f(xn+1)=',f(xn1):15:10);

readln;

end;

writeln('Kon.znach');

writeln('xn1=',xn1:15:10,'f(xn1)=',f(xn1):15:10);

readln;

end.

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