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

Министерство  образования и науки РФ

ФГБОУ ВПО

 

 

 

 

 

 

 

Информатика

 

 

 

 

 

 

 

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

ПО ДИСЦИПЛИНЕ ИНФОРМАТИКА

 

 

 

 

 

РЕШЕНИЕ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ МЕТОДОМ КАСАТЕЛЬНЫХ И ХОРД НА QBASIC

 

 

 

Выполнил:                                                                               

 

 

Проверил:                                                                               

 

 

 

 

 

Тула 2012

 

 

 

АННОТАЦИЯ

 

     Разработанный программно-методический  комплекс содержит математическое  описание, алгоритм и программу  расчёта методом хорд и касательных. Программа написана на языке Бейсик. Исходные данные вводятся с клавиатуры.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

Для заданной функции Y = f(x) на интервале [a,b] (определить самостоятельно):

1) рассчитать n значений функции с равномерным  шагом изменения аргумента x, значения  аргумента и функции представить  в виде таблицы;

2) отделить  корни уравнения f(x) = 0 аналитически, т.е. определить количество корней;

3) уточнить  корни уравнения f(x) = 0 методом  хорд и касательных с точностью  0.00001

Исходные  данные:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СОДЕРЖАНИЕ

 

 

 Общие  сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 

 Функциональное  назначение  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 

 Используемые  технические и программные средства . . . . . . . . . .

 

 Входные  и выходные данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 

 Программа  на QBasic. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .

 

 Операторы  QBasic  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 

             Список используемой литературы. . . . . . . . . . . . . . . . . . . . . . .. . . .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Общие сведения.

Метод касательных.

Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного

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

 

Описание  метода.

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

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

В предположении, что точка  приближения «достаточно близка»  к корню  , и что заданная функция непрерывна  , окончательная формула для   такова:

С учётом этого функция   определяется выражением:

Эта функция в окрестности  корня осуществляет сжимающее отображение^[1], и алгоритм нахождения численного решения уравнения   сводится к итерационной процедуре вычисления:

По теореме Банаха последовательность приближений стремится к корню уравнения  .

Геометрическая  интерпретация.

Основная идея метода заключается  в следующем: задаётся начальное  приближение вблизи предположительного корня, после чего строится касательная  к исследуемой функции в точке  приближения, для которой находится  пересечение с осью абсцисс. Эта  точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая  точность.

Пусть   — определённая на отрезке   и дифференцируемая на нём вещественнозначная функция. Тогда формула итеративного исчисления приближений может быть выведена следующим образом:

где   — угол наклона касательной в точке  .

Следовательно искомое выражение для   имеет вид:

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

 

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

Алгоритм

1. Задается начальное приближение  .
2. Пока не выполнено условие остановки, в качестве которого можно взять   или   (то есть погрешность в нужных пределах), вычисляют новое приближение:  .

 

Пример:

Рассмотрим задачу о нахождении положительных  , для которых  . Эта задача может быть представлена как задача нахождения нуля функции  . Имеем выражение для производной . Так как   для всех   и   для  , очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение  , тогда:

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

 

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

Подчёркиванием отмечены верные значащие цифры. Видно, что их количество от шага к шагу растёт (приблизительно удваиваясь с каждым шагом): от 1 к 2, от 2 к 5, от 5 к 10, иллюстрируя квадратичную скорость сходимости.

 

 

 

Метод хорд.

Пусть дано уравнение  , где - непрерывная функция, имеющая в интервале (a,b) производные первого и второго порядков. Корень считается отделенным и находится на отрезке [a,b].

Идея метода хорд состоит в том, что на достаточно малом промежутке [a,b] дугу кривой можно заменить хордой и в качестве приближенного значения корня принять точку пересечения с осью абсцисс. Рассмотрим случай (рис.1), когда первая и вторая производные имеют одинаковые знаки, т.е. .

 

 

 

 

 

 

 

 

 

 

 

Уравнение хорды - это уравнение прямой, проходящей через две точки (a, f(a)) и (b, f(b)).

Общий вид  уравнения прямой, проходящей через  две точки:

Подставляя  в эту формулу значения, получим  уравнение хорды AB:

 

.

 

Пусть x₁ - точка пересечения хорды с осью x, так как y = 0, то

x₁ может считаться приближенным значением корня.

Аналогично  для хорды, проходящей через точки  и , вычисляется следующее приближение корня:

 

В общем случае формулу метода хорд имеет вид:

                                                                (1)

Если первая и вторая производные имеют разные знаки, т.е. , то все приближения к корню выполняются со стороны правой границы отрезка (рис.2) и вычисляются по формуле:

                                                                (2)

 

 

 

 

 

 

 

 

 

 

 

 

 

Выбор формулы  в каждом конкретном случае зависит  от вида функции  и осуществляется по правилу: неподвижной является такая граница отрезка   изоляции корня, для которой знак функции совпадает со знаком второй производной. Формула (1) используется в том случае, когда . Если справедливо неравенство , то целесообразно применять формулу (2).

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

 

 

Если обозначить через m наименьшее значение |f'(x)| на промежутке     [a, b], которое можно определить заранее, то получим формулу для оценки точности вычисления корня:           

 

или

где - заданная погрешность вычислений.

 

 

 

 

 

 

 

Список идентификаторов.

a – начало отрезка,

b – конец отрезка,

eps – погрешность вычислений,

x – искомое значение корня,

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

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

x0 – точка, в которой мы ищем производную.

 

****************************************************************

Program kursovaia;

 uses crt;

 Var

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

 

{Вычисление данной функции}

Function fx(x:real): real;

  begin

   fx:=exp(x)-10*x;

  end;

----------------------------------------------------------------

{Функция вычисления производной  и определение точности вычислений}

{Для определения точности вычисления  берем значение 2-й производной  в точке x*= }

 Function proizv(x0,eps: real): real;

  var

   dx,dy,dy2: real;

  begin

   dx:=1;

   Repeat

    dx:=dx/2;

    dy:=fx(x0+dx/2)-fx(x0-dx/2);

    dy2:=fx(5*x0/4+dx)-2*fx(5*x0/4);

    dy2:=dy2+fx(5*x0/4-dx);

   Until abs(dy2/(2*dx))<eps;

    proizv:=dy/dx;

  end;

----------------------------------------------------------------

{Уточнение количества знаков  после запятой}

 Function utoch(eps:real): integer;

  var

   k: integer;

  begin

   k:=-1;

   Repeat

    eps:=eps*10;

    k:=k+1;

   Until eps>1;

  utoch:=k;

 end;

----------------------------------------------------------------

{Процедура определения наименьшего  значения производной на

 заданном промежутке}

Procedure minimum(a,b,eps: real; var min: real);

  var

   d: real;

  begin

   a:=a-eps;

   b:=b+eps;

    Repeat

     a:=a+eps;

     b:=b-eps;

     min:=abs(proizv(a,eps));

     d:=abs(proizv(b,eps));

     If min>d Then min:=d

    Until min <>0

  end;

----------------------------------------------------------------

{Процедура уточнения корня методом  хорд}

Procedure chord(a,b,eps,min: real; var x:real);

 Var

  x1: real;

 begin

  x1:=a;

   Repeat

    x:=x1-((b-x1)*fx(x1))/(fx(b)-fx(x1));

    x1:=x

   Until abs(fx(x))/min<eps

 end;

----------------------------------------------------------------

{Основная программа}

 Begin

  clrscr;

  Writeln ('Введите начало отрезка a, конец отрезка b');

  Readln (a,b);

  Writeln ('Введите погрешность измерений eps');

  Readln (eps);

  minimum(a,b,eps,min);

  chord(a,b,eps,min,x);

  Writeln ('Корень уравнения x= ',x:3:utoch(eps));

End.

****************************************************************

   После работы программы  для различных значений погрешностей, получим результаты корня x :

  0,11

  0,111

  0,1119

  0,11183

  0,111833

 

Результат вычислений в программе MathCAD дал следующее значение корня x:

x=0.112

График функции  выглядит так:

 

Поведение функции  вблизи точки пересеченья с осью ОХ выглядит так:

 

 

Алгоритм

Пользуясь рекуррентной формулой (2) и формулой  для оценки точности вычисления, составим процедуру уточнения корня методом  хорд:

Procedure chord(a, b, eps, min : real; var x : real);

Здесь  x:=x1-((b-x1)*fx(x1))/(fx(b)-fx(x1)) – рекуррентная формула,

 abs(fx(x))/min < eps – формула для оценки точности вычислений.

 

При вычислении производной функции

Function proizv(x0, eps : real) : real;

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

Таким образом, вычисляется производная в середине промежутка.

По значениям f' можно таким же способом найти  производную от f', т.е. f''. Можно выразить f'' непосредственно через f(x):

 

Для производной  третьего порядка можно использовать следующую формулу:

Здесь dx:=1 - первоначальная величина промежутка,

dx:=dx/2 – для уточнений делим промежуток на 2,

dy:=fx(x0+dx/2 -fx(x0-dx/2) – вычисление первой производной в точке x0 ,

dy2:=fx(5*x0/4+dx)-2*fx(5*x0/4)+fx(5*x0/4-dx) – вычисление второй производной, для определения точности вычисления, используется вторая производная в точке