Решение уравнений методом Ньютона



Федеральное агентство по образованию Российской Федерации

 

Уфимский государственный  авиационный технический университет

 

Кумертауский филиал

 

 

 

Кафедра ПА

 

 

 

 

 

КУРСОВАЯ РАБОТА 
по программированию и основам алгоритмизации 
на тему:

«Решение уравнений методом Ньютона (метод касательных)»

 

 

 

 

 

Выполнил: ст. гр. АТП-109

Кинзябулатов В.Р.

Проверил: ст. преподаватель 
А. Я. Митрофанов

 

Оценка: _________________

Подпись: _________________

Дата: _________________

 

 

 

 


 


СОДЕРЖАНИЕ

 

 

 

Введение

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

 

 

 

  1. Математическое описание задачи
    1. Сущность метода Ньютона.

Пусть х* есть корень уравнения f(x) = 0, единственный на отрезке [a, b].

Предположим, что каким-либо способом, например, графически определено начальное приближение x0 к корню. В этой точке вычислим значение функции f(x0) и ее производной f ′(x = x0 ) . Значение этой производной равно tgα) (см. рисунок .1) – тангенсу угла наклона соответствующей касательной к оси абсцисс. Точка x1 пересечения этой касательной с осью абсцисс есть следующее приближение к корню (поэтому метод Ньютона и называют методом касательных). Эта точка x1 принимается за новое начальное приближение и процесс повторяется. Из рисунка видно, что процесс сходится к искомому корню x*. Процесс уточнения корня закончится, когда выполнится условие

xk+1 − xk < ε,

где ε – допустимая погрешность определения корня. Из геометрических соображений можно получить расчетную формулу для метода Ньютона в виде:

    (1)

Рисунок 1. Иллюстрация метода касательных (Ньютона)

Метод Ньютона  обладает высокой скоростью сходимости. Обычно абсолютная погрешность нахождения корня ε = 10−5 … 10−6 достигается за 5 – 6 итераций. Однако существенным недостатком этого метода является необходимость вычисления производной функции на каждом шаге итерационного процесса. Это может явиться серьезным препятствием, когда функция вычисляется по очень сложному или трудоемкому алгоритму. Несколько уменьшив скорость сходимости, можно ограничиться вычислением производной только на первой итерации, а затем вести вычисления по формуле (1), полагая f '(xk ) ≈ f '(x0 ) :

 

 

  1. Словесно-формульное описание алгоритма

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

    1. Описание алгоритма

Описание входной информации: a - левая граница промежутка, b - правая граница промежутка, e - относительная погрешность. Необходимо также задать функцию и ее производную.

Алгоритм:

  1. Вводим a,b (левый и правый края промежутка);
  2. Вводим e (относительная погрешность);
  3. Присваиваем x:=a;
  4. Вычисляем значение t:=f(x)/f'(x);
  5. Вычисляем значение x:=x-t;
  6. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7
  7. Выводим на экран сообщение: «Корень уравнения x=», выводим х,
  8. Завершаем алгоритм.
    1. Выполнение алгоритма

Пример № 1.

Найти корни уравнения  на отрезке (1; 3) с точностью 0,001.

 

  1. Вводим a,b (левый и правый края промежутка) a:=1; b:=3;
  2. Вводим eps (относительная погрешность) eps:=0,001;
  3. Присваиваем x:=a (x:=1);
  4. Вычисляем значение t:=f(x)/f'(x)= f(1)/f'(1)=-1,3333;
  5. Вычисляем значение x:=x-t=1-(-1,3333)=2,3333;
  6. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

1,3333<=0.001 – нет – переходим к п.4

  1. Вычисляем значение t:=f(x)/f'(x)= f(2,3333)/f'(2,3333)=0,3137;
  2. Вычисляем значение x:=x-t=2,3333-0,3137=2,0196;
  3. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

0,3137<=0.001 – нет – переходим к п.4

  1. Вычисляем значение t:=f(x)/f'(x)= f(2,0196)/f'(2,0196)=0,0195;
  2. Вычисляем значение x:=x-t=2,0196-0,0195=2,0001;
  3. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

0,0195<=0.001 – нет – переходим к п.4

  1. Вычисляем значение t:=f(x)/f'(x)= f(2,0001)/f'(2,0001)=0,0001;
  2. Вычисляем значение x:=x-t=2,0001-0,0001=2,0000;
  3. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

0,0001<=0.001 – да – переходим к п.7

  1. Выводим на экран сообщение: «Корень уравнения x=», выводим 2,0000.
  2. Завершаем алгоритм.

 

Пример  № 2. Найти корни уравнения на отрезке (-1; 1) с точностью 0,0001.

 

  1. Вводим a,b (левый и правый края промежутка) a:=-1 b:=1;
  2. Вводим eps (относительная погрешность) eps:=0,0001;
  3. Присваиваем x:=a (x:=-1);
  4. Вычисляем значение t:=f(x)/f'(x)= f(-1)/f'(-1)=-0,4621;
  5. Вычисляем значение x:=x-t=-1-(-0,4621)=-0,5379;
  6. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

0,4621<=0.0001 – нет – переходим к п.4

  1. Вычисляем значение t:=f(x)/f'(x)= f(-0,5379)/f'(-0,5379)=0,0291;
  2. Вычисляем значение x:=x-t=-0,5379-0,0291=-0,5670;
  3. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

0,0291<=0.001 – нет – переходим к п.4

  1. Вычисляем значение t:=f(x)/f'(x)= f(-0.5670)/f'(-0.5670)=0,0000;
  2. Вычисляем значение x:=x-t=-0.5670-0,0002=-0.5672;
  3. Если модуль числа t меньше или равно значения погрешности, то перейти к п. 4. иначе к п. 7

0,0000<=0.001 – да– переходим к п.7

  1. Выводим на экран сообщение: «Корень уравнения x=», выводим -0,5672.
  2. Завершаем алгоритм.

 

 

 

    1. Выводы по результатам выполнения алгоритма

 

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

 

 

 

  1. Блок-схема алгоритма

Запись алгоритмов в виде блок-схем является наиболее наглядным видом  записи. В то же время этот способ является и наиболее громоздким.

    1. Блок-схема алгоритма

 

 

 

 

 

 

 

 

 

 

    1. Выполнение алгоритма, записанного в виде блок-схемы

 

Пример  № 1. Найти корни уравнения на отрезке (1; 3) с точностью 0,001.

 

Шаг

Блок 

Действие 

Переход  
(связь)

Переменные 

1.

1

начало

2

  

2.

2

Ввод а=1, b=3, eps=0.001

3

а=1

b=3

eps=0.001

3.

3

x:=a

4

x=1

4.

4

t:=f(x)/f'(x)

x:=x-t

5

t=-1,3333

x=2,3333

5

5

Проверка условия | t | <=eps

Нет

Переход к блоку 4

 

6

4

t:=f(x)/f'(x)

x:=x-t

5

t=0,0195

x=2,0001

7

5

Проверка условия | t | <=eps

Нет

Переход к блоку 4

  

8

4

t:=f(x)/f'(x)

x:=x-t

5

t=0,0001

x=2,0000

9

5

Проверка условия | t | <=eps

Да

Переход к блоку 6

  

10

6

Вывод x

7

x=2.0000

11

7

Конец

    

 

 

Пример  № 2. Найти корни уравнения на отрезке (-1; 1) с точностью 0,0001.

Шаг

Блок 

Действие 

Переход  
(связь)

Переменные 

1.

1

начало

2

  

2.

2

Ввод а=-1, b=1, eps=0.0001

3

а=-1

b=1

eps=0.0001

3.

3

x:=a

4

x=-1

4.

4

t:=f(x)/f'(x)

x:=x-t

5

t=-0,4621

x=-0,5379

 

5

5

Проверка условия | t | <=eps

Нет

Переход к блоку 4

 

6

4

t:=f(x)/f'(x)

x:=x-t

5

t=0,0291

x=-0,5670

 

7

5

Проверка условия | t | <=eps

Нет

Переход к блоку 4

  

8

4

t:=f(x)/f'(x)

x:=x-t

5

t=0,0000

x=-0.5672

 

9

5

Проверка условия | t | <=eps

Да

Переход к блоку 6

  

10

6

Вывод x

7

x=-0.5672

11

7

Конец

    

 

 

 

 

  1. Описание алгоритма на алгоритмическом языке

Алгоритмический язык, использующийся в данной работе, является наиболее приближенным, по сравнению со всеми остальными приведенными формами, к языку программирования – конкретно к языку Turbo Pascal.

    1. Описание алгоритма

Алгоритм Newton;

 

Переменные a,b,eps,t,x,f,f1;

 

НАЧАЛО

 

ПишиСтр (a,b,eps);

 

x:=a;

Повторяй 

t:=f(x)/f1(x);

x:=x-t;

до тех  пор пока не выполнится условие| t | <=eps

ПишиСтр (x);

КОНЕЦ

 

 

 

    1. Выполнение алгоритма, записанного на алгоритмическом языке

Пример  № 1. Найти корни уравнения на отрезке (1; 3) с точностью 0,001.

 

№ п/п 

Команды

Переменные 

На экране

1.

ПишиСтр (a,b,eps)

а=1

b=3

eps=0.001

  

2.

x:=a

x:=1

  

3.

t:=f(x)/f'(x)

x:=x-t

t=-1,3333

x=2,3333

  

4

Проверка условия | t | <=eps - нет

    

5

t:=f(x)/f'(x)

x:=x-t

t=0,0195

x=2,0001

  

6

Проверка условия | t | <=eps - нет

    

7

t:=f(x)/f'(x)

x:=x-t

t=0,0001

x=2,0000

  

8

Проверка условия | t | <=eps – да

    

9

ПишиСтр (x)

x=2,0000

2,0000


 

Пример  № 2. Найти корни уравнения на отрезке (-1; 1) с точностью 0,0001.

№ п/п 

Команды

Переменные 

На экране

1.

ПишиСтр (a,b,eps)

а=-1

b=1

eps=0.0001

  

2.

x:=a

x:=-1

  

3.

t:=f(x)/f'(x)

x:=x-t

t=-0,4621

x=-0,5379

  

4

Проверка условия | t | <=eps - нет

    

5

t:=f(x)/f'(x)

x:=x-t

t=0,0291

x=-0,5670

 

  

6

Проверка условия | t | <=eps - нет

    

7

t:=f(x)/f'(x)

x:=x-t

t=0,0000

x=-0.5672

 

  

8

Проверка условия | t | <=eps – да

    

9

ПишиСтр (x)

x=-0.5672

-0.5672


 

    1. Выводы по результатам выполнения алгоритма

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

 

  1. Реализация алгоритма на языке Pascal
    1. Краткое описание языка программирования

Язык программирования Pascal был разработан в 1968-1971 гг. Никлаусом  Виртом в Цюрихском Институте информатики (Швейцария), и назван в честь Блеза Паскаля – выдающегося математика, философа и физика 17-го века. Первоначальная цель разработки языка диктовалась необходимостью создания инструмента "для обучения программированию как систематической дисциплине". Однако очень скоро обнаружилась чрезвычайная эффективность языка Pascal в самых разнообразных приложениях, от решения небольших задач численного характера до разработки сложных программных систем - компиляторов, баз данных, операционных систем и т.п. К настоящему времени Pascal принадлежит к группе наиболее распространенных и популярных в мире языков программирования:

  • существуют многочисленные реализации языка практически для всех машинных архитектур;
  • разработаны десятки диалектов и проблемно-ориентированных расширений языка Pascal;
  • обучение программированию и научно-технические публикации в значительной степени базируются на этом языке.

Характеристика  и особенности языка

Существует ряд объективных  причин, обусловивших выдающийся успех  языка Pascal. Среди них в первую очередь необходимо указать следующие:

  • Язык в естественной и элегантной форме отразил важнейшие современные концепции технологии разработки программ:

a. развитая система  типов, 

b. ориентация на принципы  структурного программирования,

c. поддержка процесса  пошаговой разработки.

Благодаря своей компактности, концептуальной целостности и ортогональности понятий, а также удачному первоначальному описанию, предложенному автором языка, Pascal оказался весьма легок для изучения и освоения. В противоположность громоздким многотомным описаниям таких языков, как PL/l, Cobol, FORTRAN, достаточно полное описание языка Pascal занимает около 30 страниц текста, а его синтаксические правила можно разместить на одной странице.

  • Несмотря на относительную простоту языка, он оказался пригоден для весьма широкого спектра приложений, в том числе для разработки очень больших и сложных программ, например, операционных систем.
  • Pascal весьма технологичен для реализации практически для всех, в том числе и нетрадиционных, машинных архитектур. Утверждается, что разработка Pascal-транслятора "почти не превышает по трудоемкости хорошую дипломную работу выпускника вуза". Благодаря этому для многих ЭВМ существует несколько различных реализаций языка, отражающих те или иные практические потребности программистов.

Язык Pascal стандартизован во многих странах. В 1983 году был принят международный стандарт (ISO 7185:1983)

Основные особенности  языка Pascal

Pascal является традиционным  алгоритмическим языком программирования, продолжающим линию Algol-60. Это означает, что программа на языке Pascal представляет собой специально организованную последовательность шагов по преобразованию данных, приводящую к решению некоторой задачи. Это отличает Pascal от так называемых непроцедурных языков типа Prolog, по существу, представляющих собой формализмы для записи начальных условий некоторой задачи и синтезирующих решение посредством встроенных механизмов логического вывода.

Язык Pascal содержит удобные  средства для представления данных. Развитая система типов позволяет адекватно описывать данные, подлежащие обработке, и конструировать структуры данных произвольной сложности. Pascal является типизированным языком, что означает фиксацию типов переменных при их описании, а также строгий контроль преобразований типов и контроль доступа к данным в соответствии с их типом (как на этапе компиляции, так и при исполнении программ).

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

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

Паскаль – компилятор, то есть, прежде чем начать испоолнение программы, Паскаль полностью прочитывает исходный текст, написанный программистом, и составляет последовательность машинных кодов, выполняющую те действия, которые описал программист в hqundmnl тексте. Эта последовательность сохраняется в файл с расширением “.EXE” и является самостоятельным исполняемым файлом, который может быть запущен сам по себе, уже без участия Паскаля и, даже, на другом компъютере, на котором Паскаль может быть не установлен.

 

    1. Листинг программы

uses crt;

var

a,b,eps,x,t:real;

function f(x:real):real;

 begin

 {Здесь приводится выражение для вычисления функции}

  f:=exp(x)+x;

 end;

function f1(x:real):real;

 begin

 {Здесь приводится выражение для производной функции}

  f1:=exp(x)+1;

 end;

 

begin

 clrscr;

 writeln('Решение уравнения методом Ньютона');

 write('Введите a = ');

 read(a);

 write('Введите b = ');

 read(b);

 write('введите погрешность eps = ');

 read(eps);

 x:=a;

 repeat

  t:=f(x)/f1(x);

  x:=x-t;

 until abs(t)<=eps;

 writeln('Корень уравнения x = ', x:4:4);

end.

 

    1. Тестовые запуски программы

 

Пример № 1. Найти корни уравнения на отрезке (1; 3) с точностью 0,001.

 

Пример № 2. Найти корни уравнения на отрезке (-1; 1) с точностью 0,0001.

 

 

 

 

Заключение

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

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

 

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

 

 

    1. В.Ф. Ляхович. Основы информатики. – Р.-на-Д.: Феникс, 1996.
    2. Е.В. Алтухов, А.А. Рыбалко, В.С. Савченко. ОИВТ. – М.: Высшая школа, 19
    3. И.Г. Семакин, А.П. Шестаков. Основы программирования. – М., 2003.
    4. Острейковский В.А. Информатика. – М.: Высшая школа, 2000
    5. http://revolution.allbest.ru/programming/0000030492.html
    6. http://www.osnpas.com/file22.html
    7. http://vtit.kuzstu.ru/books/shelf/129/doc/glava2.html
    8. http://shara.org.ua/referats/ru/show/
    9. http://pcfu.ru/tag/chislennye-metody/