|
-∞
|
-7
|
-1
|
+1
|
7/5
|
+7
|
+∞
|
|
-
|
-
|
-
|
+
|
+
|
+
|
Из
таблицы 2.1 видно, что уравнение имеет один действительный
корень: X01
(-1;1).
Следовательно, X01(-1;1).
2.2 Уточнение приближенного корня
Искомый
корень уравнения (2.1) отделен, т.е. найден отрезок [а, b],
на котором имеется один и только один корень уравнения. Любую точку этого
отрезка можно принять за приближенное значение корня. Погрешность такого
приближения не превосходит длины [а, b]. Следовательно, задача
отыскания приближенного значения корня с заданной точностью E
сводится к нахождению отрезка [а, b], удовлетворяющего условие
|b-а|<E (2.2)
Эту задачу называют задачей уточнения корня. На практике широкое
распространение получили следующие методы:
1) метод половинного деления;
2) метод Ныотона (метод касательных);
3) метод хорд;
4) комбинированный метод хорд и касательных;
5) метод простой итерации.
.3 Метод
касательных (метод Ньютона)
Метод Ньютона, или метод касательных, является наиболее часто применяемым
методом уточнения корней, пригодным для решения алгебраических и
трансцендентных уравнений.
В дальнейшем будем считать, что искомый корень x0 уравнения (2.1) отделен отрезком [а,
b], на котором функция f(x) удовлетворяет следующим условиям:
) непрерывна вместе со своими производными до второго порядка,
включительно;
) на концах отрезка принимает значения различных знаков;
) производные отличны от нуля и сохраняют определенный знак.
Геометрически это означает, что график функции у = f(x) в любой точке отрезка [а, b] имеет касательную и не имеет экстремумов и точек перегиба
(рис. 2.1).
Рис. 2.1 - График функции у = f(x)
За
первое приближение корня положим такое значение x1, (x1 [а, b]), при котором
знаки функции f(x1) и ее второй производной f ''(x1) совпадут, и через точку M1(X1,f(x1)) проведем касательную к кривой. Уравнение
касательной:
-
f(x1) = f '(x1)∙(x - x1).
Найдем
точку x2 пересечения
касательной с осью абсцисс. Учитывая, что
y2 = 0, получим
f(x1) = f '(x1)∙(
x2- x1).
Отсюда
получаем второе приближение корня
x2 = x1 - f(x1)/ f '(x1).
Через
точку M2(x2 , f(x2)) снова
проводим касательную к кривой, точка пересечения которой с осью Ох даст нам
третье приближение корня, и т. д.
Продолжив
описанный процесс построения касательных и в вычисления точек их пересечения с
осью Ох, получим формулу итерационного метода Ньютона:
,
n = 1, 2, 3, … (2.3)
Если первое приближение выбрано достаточно близко к корню, то метод
Ньютона всегда сходится.
Отметим
одно важное достаточное условие сходимости метода Ньютона. Пусть f(a) -f(b)<0,
а f '(x) и f '' (x) отличны от нуля и сохраняют определенные знаки на
отрезке [а, b]. Тогда для любого х [а, b],
удовлетворяющего условию:
f (x1) f '' (x1) > 0, (2.4)
метод сходится.
При выполнении условия (2.4) приближение xn+1 будет лежать между xn и x0, т. е. ближе к корню, поэтому при возрастании n приближение xn монотонно стремится к точному решению. Неудачный
выбор начального приближения x1 (x1 = а, рис. 2.2) может привести к
тому, что последующие приближения выйдут за пределы отрезка [а, b].
Обозначим через М наибольшее значение | f "(х)|, а через т - наименьшее значение | f '(х)| на отрезке [а, b]. Тогда абсолютные погрешности двух
последовательных приближений хn и xn+1 связаны неравенством
(2.5)
Оценка (2.5) показывает, что погрешность аппроксимации (ограничения)
каждого нового приближения уменьшается пропорционально квадрату погрешности
предыдущего. Поэтому, если начальное приближение х выбрано так, что
,
то
каждое новое приближение удваивает число верных десятичных знаков, т. е.
сходимость будет квадратичной. Следовательно, метод Ньютона обеспечивает
быструю сходимость, если известно хорошее начальное приближение корня.
Если
два последовательных приближения xn+1 и xn ,
полученные по методу Ньютона, совпадают с точностью E, то это еще не
гарантирует совпадения с той же точностью приближения xn+1 с точным решением x0. Для оценки погрешности можно воспользоваться
следующим неравенством
(2.6)
Таким образом, для определения корня уравнения (2.1) по методу Ньютона с
точностью E итерационный процесс продолжаем до
тех пор, пока не получим:
(2.7)
Если x0 - кратный корень уравнения (2.1), то
метод Ньютона имеет линейную сходимость, т. е. сходится со скоростью
геометрической прогрессии.
Заметим, что если производная f '(х) мало изменяется на [а, b], и ее вычисление громоздко, то итерации можно проводить по формуле:
, n =
1, 2, 3, … (2.8)
Итерационную схему (2.8) называют модифицированным методом Ньютона.
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
3.1 Описание алгоритма и структуры программы
Рассмотрим структуру программы в виде блок-схемы (рис.4.1):
Рис. 4.1 - Структурная схема программы
Описание структуры программы:
С начала работы программы, в блоке №1, вводятся коэффициенты уравнения и
максимальное значение степени. После чего, в блоке №2, выводятся на экран
уравнение, с помощью функции вывода уравнения, которая будут рассмотрены в
подразделе 4.2. После этого, в блоке №3, вводится диапазон, в котором следует
искать корень уравнения и задается точность, с которой нужно найти корень.
Далее сначала проверяется условие сходимости метода касательных, в блоке №4,
если условие не выполняется, то выводится, сообщение о неприменимости метода
касательных (блоке №6), и программа завершает свою работу (блок №9), а если
выполняется, то потом приближенный корень уточняется методом касательных (блок
№5). После нахождения корня уравнения ответ выводится на экран (блок №7). После
вывода корня программа предложит снова найти корень в заданном диапазоне (блок
№8). В случае согласия весь цикл уточнения приближенного корня начинает свою
работу с начала. В случае не согласия программа завершает свою работу (блок
№9).
Рассмотрим более подробно некоторые блоки.
Рассмотрим блок № 4.
Этот блок служит для проверки сходимости метода касательных. В начале
производятся подсчеты для значения функции f(a) и f(b), эти значения присваиваются соответственно переменным f_a и
f_b. Затем производятся подсчеты для производной первого порядка, значения f’(a) f’(b) присваиваются переменным f_a_1 и f_b_1 соответственно. После этого
производятся подсчеты для производной второго порядка, значения f''(a) f’’(b) присваиваются переменным f_a_2 и f_b_2 соответственно. После
произведенных действий проверяется условие 2.4, если это условие не
выполняется, то программа выводит сообщение о неприменимости метода касательных
и инициализирует выход.
Рассмотрим блок № 5.
Этот блок служит для уточнения корня уравнения методом касательных.
Рассмотрим блок-схему алгоритма уточнения корня уравнения методом
касательных(рис.4.3):
Рис. 4.3 - Блок-схема алгоритма уточнения корня уравнения методом
касательных
3.2 Описание разработанных функций
Функция вывода набора символов:charline(char ch, int n) - c помощью данной функции выводится
заданное количество определенных символов, где ch - задаваемый символ, а n -
количество этих символов.
Функция вывода уравнения:cout_equation(int coef[256], int power) - c помощью данной функции на экран
выводится уравнение, где coef - массив коэффициентов заданного уравнения, а power - максимальное значение степени.
Функция подсчёта значения функции:f(int array[256], int n, float x, float
func[2]) - c помощью данной функции
подсчитывается значение функции, где array - массив коэффициентов заданного
уравнения, n - максимальное значение степени, x - значение которое нужно подсчитать,
func - массив в который будет записано значение функции. Полученное значение
записывается в массив func и присваивается значению func[0].
Функция подсчёта значения производной первого порядка:derivative_1(int
array[256], int n, float x, float func[2]) - c помощью данной функции подсчитывается значение производной
первого порядка, где array - массив коэффициентов заданного уравнения, n - максимальное значение степени, x - значение которое нужно подсчитать,
func - массив в который будет записано значение функции. Полученное значение
записывается в массив func и присваивается значению func[1].
Функция подсчёта значения производной второго порядка:derivative_2(int
array[256], int n, float x, float func[2]) - c помощью данной функции подсчитывается значение производной
второго порядка, где array - массив коэффициентов заданного уравнения, n - максимальное значение степени, x - значение которое нужно подсчитать,
func - массив в который будет записано значение функции. Полученное значение
записывается в массив func и присваивается значению func[2].
При написании программы часто использовались функции. Функция
представляет собой именованное объединение группы операторов. Это объединение
может быть вызвано из других частей программы.
Наиболее важной причиной использования функций служит необходимость
концептуализировать структуру программы, то есть сократить размер программного
кода. Любая последовательность операторов, встречающаяся в программе более
одного раза, будучи вынесенной, в отдельную функцию, сокращает размер
программы. Код функции хранится только в одной области памяти.
Для использования дополнительных функций обязательными являются три
компонента: объявление функции, её определение и вызов. Не возможно
использовать переменную, не сообщив компилятору информацию о ней, и не возможно
обратится к функции, не указав в программе её необходимые атрибуты. Есть два
способа описать функцию: объявить и определить функцию до первого её вызова.
Объявление функции означает, что где-то ниже будет содержаться код этой
функции. Ключевое слово void
указывает на то, что функция не возвращает значения, а пустые скобки говорят об
отсутствии у функции передаваемых аргументов. Объявление функции заканчивается
точкой с запятой (;) и на самом деле является обычным оператором.
Объявления функций также называют прототипами функций, поскольку они
являются общим представлением или описанием функций. Прототип говорит
компилятору о том, что функция будет написана позже, и можно вызывать эту
функцию до того, как будет обнаружен её код.
Для того чтобы вызвать функцию необходимо только имя функции и круглые
скобки. Вызов функции внешне очень похож на прототип; разница заключается лишь
в том, что при вызове не указывается тип возвращаемого значения. Вызов функции
завершается точкой с запятой (;). Выполнение оператора вызова функции
инициирует выполнение самой функции. Это означает, что управление передаётся
операторам функции, которые после своего выполнения, в свою очередь, передают
управление оператору, следующему за вызовом функции.
Определение функции состоит из заголовка и тела функции. Тело функции
состоит из последовательности операторов, заключённой в фигурные скобки.
Заголовок функции должен соответствовать её прототипу: имя функции и тип
возвращаемого ей значения должны совпадать с указанными в прототипе; кроме
того, аргументы функции, если они есть, должны иметь те же типы и следовать в
том же порядке, в каком они были указаны в прототипе. Когда происходит вызов
функции, программа передаёт управление первому оператору тела функции. Затем
исполняются операторы, находящиеся в теле функции, и когда достигается
закрывающаяся фигурная скобка, управление передаётся обратно вызывающей
программе.
Объявления библиотечных функций содержатся в заголовочных файлах,
подключаемых к программе. Определение, уже скомпилированное в исполняемый код,
находится в библиотечном файле, содержимое которого автоматически
прикомпоновывается к исполняемому коду программы. Если использовать
библиотечную функцию, не нужно создавать её объявление и определение, но когда
нужно разработать свою собственную функцию, и объявление, и определение этой
функции должны присутствовать в исходном тексте программы. Вторым способом
вставить функцию в программу является её определение, помещённое ранее первого
её вызова. В этом случае прототип функции не используется.
Аргументом называют единицу данных, передаваемую программой в функцию.
Аргументы позволяют функции оперировать различными значениями или выполнять
различные действия в зависимости от переданных ей значений. В скобках указаны
типы данных, которые будут иметь передаваемые в функцию аргументы: например, char или int. При вызове функции вместо аргументов в скобках указываются
их конкретные значения. Переменные, используемые внутри функции для хранения
значений аргументов, называются параметрами. Типы переменных, используемых в
качестве аргументов функции, должны, как и в случае констант, совпадать с
типами, указанными в объявлении и определении функции.
Как и в случае с константами, функция имеет две переменные для хранения
переданных значений. Типы и имена этих переменных указаны в прототипе при
определении функции. Способ передачи, аргументов при котором функция создаёт
копию передаваемых значений, называется передачей аргументов по значению.
Ссылка является псевдонимом, или альтернативным именем переменной. Одним
из наиболее важных применений ссылок является передача аргументов в функции.
Когда осуществляется передача по значению, вызываемая функция создаёт новые
переменные, имеющие те же типы, что и передаваемые аргументы, и копирует
значения аргументов в эти переменные. Функция не имеет доступа к
переменным-аргументам, а работает со сделанными ей копиями значений. Передача
аргументов по ссылке происходит по другому механизму. Вместо того чтобы
передавать функции значение переменной, ей передаётся ссылка на эту переменную.
Существование функций делает возможным использование такого средства
программирования, как рекурсия. Рекурсией называют способ задания функций при
котором значение определяемой функции для произвольных значений аргумента
выражается известным образом, через значение определённой функции для меньших
значений аргументов. Рекурсия позволяет функции вызывать саму себя на
выполнение. Каждый экземпляр функции хранит своё значение параметра во время
выполнения рекурсивного вызова. Каждая рекурсивная функция должна включать в
себя условие окончания рекурсии. В противном случае рекурсия будет происходить
бесконечно, что приведёт к аварийному завершению программы. В памяти будут
находиться значения параметров для каждого из вызовов, однако тело функции
будет присутствовать в памяти в единственном экземпляре.
Область видимости определяет, из каких частей программы возможен доступ к
переменной, а класс памяти - время, в течении которого переменная существует в
памяти компьютера.
4. ИНСТРУКЦИЯ
ПОЛЬЗОВАТЕЛЯ
Общее описание:
Программа предназначена для решения нелинейных уравнений вида:
Pn(x)=0 ,
где Pn(x)
- многочлен: n(x)=a0xn+a1xn-1+...+an-1+an,
a0≠0
Например: x5+5x4-2x3-4x2+7x-3=0
Системные требования:
ОC: Windows 95/98/ME/2000/XP/2003
Процессор: Intel (или любой совместимый) 100Mhz
Память: 32mb RAM: 600 кб
Описание работы программы:
Для работы с программой необходимо запустить приложение program.exe
После запуска программы необходимо ввести максимальное значение степени
уравнения и его коэффициенты. После чего программа выведет это уравнение на
экран. Далее программа попросит ввести диапазон, где расположен корень
уравнения, после ввода программа выведет найденный корень уравнения и предложит
найти его еще раз, в другом диапазоне. Если функция меняет знак в разных
местах, то корней будет несколько, следует воспользоваться этим предложением.
ВЫВОДЫ
нелинейное уравнение метод касательная программный
Метод решения нелинейных уравнений, такой как метод касательных (метод
Ньютона), хорошо изучен. Приобретены более обширные теоретические знания.
В результате работы удалось создать программу для нахождения корней нелинейных
уравнений при помощи метода касательных. Были разработаны полезные функции,
например, такие как функция подсчета производной для первого и для второго
порядка.
Данную программу можно применить в учебных целях и в помощь инженеру.
СПИСОК ЛИТЕРАТУРЫ
1. Верлань
А. Ф. Інформатика: Підручник / А.Ф. Верлань, Н.В. Апатова. - К.: Форум, 2000. - 224 с.: іл.
2. Лафоре
Р. Объектно-ориентированное программирование в С++ / Р. Лафоре. - 4-е изд. -
М.: Питер, 2003. - 923 с.: ил. -
(Классика Computer Science).
3. Путятин
Е.П. Турбо Паскаль в курсе высшей
математики: Учеб. пособие / Е.П. Путятин, Д.М. Смагин, В.П. Степанов - Харьков: Каравелла, 1997. -352с.
4. Страуструп
Б. Язык программирования С++ / Б. Страуструп. - 3-е изд., доп. - СПб.: Бином,
1999 . - 991с.
ПРИЛОЖЕНИЕ А. ТЕКСТ ПРОГРАММЫ
#include <iostream>
using namespace std;
#include <math.h>
//функции вывода набора символов
void charline(char ch, int n)
{( int j=0; j<=n; j++ )
cout<<ch;<<endl;
}
//функция вывода уравнения
void cout_equation(int coef[256], int power)
{temp_power=power; //присваивание переменной temp_power значение
степени<<"\nf(x) = ";(coef[0]!=1) //выводить первый коеффициент
если он не равен "1"
{(coef[0]!=-1) //если коеффициент не равен "-1"
{cout<<coef[0];} //иначе вывести знак "-"
{cout<<"-";}
}<<"x";(temp_power>1) //выводить степень, если она
больше "1"
{cout<<"^"<<temp_power--;}
for(int i=1;i<power;i++)
{
if(coef[i]>0)
//если коеффициент положительный
{cout<<"+"<<coef[i];} //то прибавить знак
"+"
else
{cout<<coef[i];}
cout<<"x";
if(temp_power>1)
//выводить степень, если она больше "1"
{cout<<"^"<<temp_power--;}
}(coef[power]>0) //если вольный член положительный
{cout<<"+"<<coef[power]<<"\n";}
//то прибавить знак "+"
else
{cout<<coef[power]<<"\n";}
}
//функция подсчёта значения функцииf(int array[256], int n, float x, float func[2])
{temp_power=n;temp_root;temp=0;(int i=0; i<n; i++)
{
temp_root=temp+array[i]*pow(x,temp_power);
temp_power--;
}[0]=temp+array[n];
}
//функция подсчёта значения производной первого порядка
void derivative_1(int array[256], int n, float x, float
func[2])
{temp_power=n;temp_root;temp=0;(int i=0; i<n-1; i++)
{
temp_root=temp+temp_power*array[i]*pow(x,temp_power-1);
temp=temp_root;
temp_power--;
}[1]=temp+array[n-1];
}
//функция подсчёта значения производной второго порядка
void derivative_2(int array[256], int n, float x, float
func[2])
{temp_power=n;temp_root;temp=0;(int i=0; i<n-2; i++)
{
temp_root=temp_power*array[i]*(temp_power-1)*pow(x,temp_power-2)+temp;
temp=temp_root;
temp_power--;
}[2]=array[n-2]*(n-3)+temp;
}
main()
{('-',66);<<" The decision of the nonlinear
equation by method of tangents\n";('-',66);
coef[256], power;<<"Input maximal value of power:
";>>power; //ввод максимального значения степени<<"Input values of factors:\n";(int
i=0;i<power;i++)
{<<i+1<<" factor: ";>>coef[i]; //ввод коэффициентов уравнения
}<<"Free member: ";>>coef[power]; //ввод вольного члена уравнения('-',66);<<" Desicion\n";('-',66);
_equation(coef, power); //вывод уравнения
func[2];
again;
//Method of tangents
(again!='n'){a, b, x, E, S, root, f_a, f_b, f_a_1, f_a_2,
f_b_1, f_b_2;<<"Enter a range of values [a,b] in which the root of
the equation is located: \n";<<"a =
";cin>>a;<<"b = ";cin>>b;<<"Input accuracy: ";cin>>E;
//-----------условие сходимости метода касательных-----------//
f(coef, power, a, func);_a=func[0];(coef, power, b,
func);_b=func[0];
_1(coef, power, a, func);_a_1=func[1];_2(coef, power, a,
func);_a_2=func[2];
_1(coef, power, b, func);_b_1=func[1];_2(coef, power, b,
func);_b_2=func[2];
(f_a*f_b>0 || f_a_1==0 || f_a_2==0 || f_b_1==0 ||
f_b_2==0)
{
cout<<"The method of tangents(Nuton's method)
is not applicable"<<endl;
break;
}
//-------------------------------------------------------------//n=0;min_a,
min_b, min;=a;_1(coef, power, x, func);_a=func[1];=b;_1(coef, power, x,
func);_b=func[1];(fabs(min_a)>fabs(min_b))
{min=fabs(min_b);}
{min=fabs(min_a);}
max_a, max_b, max;=a;_2(coef, power, x,
func);_a=func[2];=b;_2(coef, power, x, func);_b=func[2];(fabs(max_a)>fabs(max_b))
{max=fabs(max_a);}
{max=fabs(max_b);}
=sqrt((2*min*E)/max);
roots[64]; =b;_1(coef, power, x, func);_b_1=func[1];_2(coef,
power, x, func);_b_2=func[2];(f_b_1*f_b_2>0)
{root=b;}
{
x=a;
derivative_1(coef, power, x, func);
f_a_1=func[1];
derivative_2(coef,
power, x, func);
f_a_2=func[2];
if(f_a_1*f_a_2<0)
{root=a;}
}(fabs(roots[n]-root<S)){=n+1;(n>1)
{root=roots[n];}(coef,power, root, func);_1(coef, power,
root, func);[n]=root-(func[0]/func[1]);
}i=n;<<"x = "<<roots[i]<<endl;<<"Do
you want to find a root in the set range again?(y/n)"; cin>>again;
}
}