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

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

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

на тему

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

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

Виконав: студентка 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А.

0

Рис. 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=¾.

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

x

-?

-1

¾

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,78 788

0,212 121

3,71772E-06

-1,78 788

1,1 760 227

-22,297 965

45,8 546

-1,73 514

0,52 741

-1,73 514

0,615 176

-19,987 538

42,53 931

-1,73 206

0,3 078

-1,73 206

0,2 013

-19,856 836

42,39 279

-1,73 205

1,01E-05

-1,73 205

2,177E-09

-19,856 406

42,3923

-1,73 205

1,1E-10

-1,73 205

-3,55E-15

-19,856 406

42,3923

-1,73 205

0

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

Рассмотрим промежуток [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,737 755 102

-0,62 244 898

1,737 755

0,45 167 903

7,980 242 552

21,81 098 292

1,732 095 136

-0,5 659 966

1,732 095

0,348 282

7,857 364 326

21,6 092 719

1,73 205 081

-4,43255E-05

1,732 051

2,12279E-08

7,856 406 519

21,60 769 525

1,732 050 808

-2,70199E-09

1,732 051

0

7,856 406 461

21,60 769 515

1,732 050 808

0

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

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

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

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

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

Eps — константа, равная 0,1, типа 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 Блок-схема программы

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

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

Для f

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

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

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. 1

xn= -1. 7 878 787 879 xn+1= -1. 7 351 386 122 f (xn+1)= 0. 615 150 328

xn= -1. 7 351 386 122 xn+1= -1. 7 320 609 420 f (xn+1)= 0. 2 012 359

xn= -1. 7 320 609 420 xn+1= -1. 7 320 508 077 f (xn+1)= 0. 22

xn= -1. 7 320 508 077 xn+1= -1. 7 320 508 076 f (xn+1)= 0. 0

xn= -1. 7 320 508 076 xn+1= -1. 7 320 508 076 f (xn+1)= 0. 0

Kon. znach

xn1= -1. 732 050 8076f (xn1)= 0. 0

Vtoroy koren

Ot A= 1. 0000 do B= 2. 0000

Pogrewnost E 0. 1

xn= 1. 8 000 000 000 xn+1= 1. 7 377 551 020 f (xn+1)= 0. 451 679 035

xn= 1. 7 377 551 020 xn+1= 1. 7 320 951 358 f (xn+1)= 0. 3 482 818

xn= 1. 7 320 951 358 xn+1= 1. 7 320 508 103 f (xn+1)= 0. 212

xn= 1. 7 320 508 103 xn+1= 1. 7 320 508 076 f (xn+1)= 0. 0

xn= 1. 7 320 508 076 xn+1= 1. 7 320 508 076 f (xn+1)= 0. 0

Kon. znach

xn1= 1. 732 050 8076f (xn1)= 0. 0

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

Первый корень

Второй корень

Excel

Pascal

Excel

Pascal

-1,78 788

-1. 7 878 787 879

1,8

1. 8 000 000 000

-1,73 514

-1. 7 351 386 122

1,737 755 102

1. 7 377 551 020

-1,73 206

-1. 7 320 609 420

1,732 095 136

1. 7 320 951 358

-1,73 205

-1. 7 320 508 077

1,73 205 081

1. 7 320 508 103

-1,73 205

-1. 7 320 508 076

1,732 050 808

1. 7 320 508 076

-1,73 205

-1. 7 320 508 076

1,732 050 808

1. 7 320 508 076

Нижняя выделенная строка содержит окончательный ответ 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. 1;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. 1;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.

ПоказатьСвернуть
Заполнить форму текущей работой