Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 12
Утверждаю
Ректор университета
_______________А.В. Лагерев
«______»_____________2007г.
Методические указания
к выполнению лабораторной работы №3
для студентов очной формы обучения
специальности 230201 – "Информационные системы
и технологии"
Брянск 2007
УДК 004.43
Алгоритмические языки и программирование. Итерационные методы решения задач: методические указания к выполнению лабораторной работы №3 для студентов очной формы обучения специальности 230201 – "Информационные системы и технологии". – Брянск: БГТУ, 2007. - 12 с.
Разработали: Ю.А. Леонов, асс.
С.М. Рощин, к.т.н.
Научный редактор Ю.М. Казаков
Редактор издательства Л.И. Афонина
Компьютерный набор Ю.А. Леонов
Рекомендовано кафедрой «Компьютерные технологии и системы» БГТУ (протокол № от )
Темплан 2007г., п. 458
|
Подписано в печать Формат 60х84 1/16. Бумага офсетная. Офсетная печать. Усл. печ. л. 0,7 Уч. – изд. л. 0,7 Тираж 50 экз. Заказ Бесплатно |
Издательство брянского государственного технического университета, 241035, Брянск, бульвар 50-летия Октября, 7, БГТУ. 58-82-49
Лаборатория оперативной полиграфии БГТУ, ул. Харьковская, 9
Целью работы является ознакомление с итерационными методами нахождения результата на примере вычисления суммы сходящегося ряда и нахождение корней нелинейных уравнений.
Продолжительность работы – 6ч.
2.1. Числовые ряды
Если существует конечный предел частичных сумм , то число вой ряд называется сходящимся и его сумма равна значению этого предела, иначе ряд называется расходящимся. Если ряд сходится, т.е. имеет сумму S, то пишут
S=u1+u2+u3+…+un+…,
где u1, u2, u3 … - члены сходящегося ряда.
2.2. Итерационные методы
Для решения систем алгебраических уравнений, нахождения экстремумов функций и т.д. существуют прямые и итерационные методы.
Прямые методы позволяют получить точное решение, выполнив конечное число операций. Примером прямого метода может служить правило Крамера для решения системы совместных линейных алгебраических уравнений. Обычно для сложных систем уравнений прямые методы неэффективны, так как при их применении требуется выполнение огромного объема вычислений. Поэтому чаще пользуются итерационными методами.
Сущность итерационных методов заключается в многократном повторении одного и того же простого алгоритма, который дает результат, постепенно приближающийся к точному решению. Итерации начинаются с задания начального приближенного решения. Затем начальные значения переменных последовательно изменяются, пока не достигается заданная точность решения. Быстрота сходимости итерационного метода сильно зависит от степени точности начальной аппроксимации.
2.3. Решение нелинейных уравнений
Любое уравнение можно представить в виде (x)=0, если перенести все компоненты уравнения в одну сторону, тогда поиск корней уравнения сводится к поиску точек пересечения функции (x) с осью абсцисс.
В случае, когда невозможно или крайне затруднителен поиск прямых методов решения для нахождения корней нелинейных уравнений, применяют итерационные методы решения. Ниже представлены три итерационных метода решения нелинейных уравнений: метод половинного деления, метод Ньютона (метод касательных) и модифицированный метод Ньютона (метод хорд).
Существует ряд методов численного решения нелинейных уравнений, целесообразность применения каждого из которых определяется видом уравнения, его порядком, требуемой точностью и т.д.
Возможность нахождения корня уравнения заданным методом строится на утверждении, что функция, пересекающая ось абсцисс, имеет различные знаки функции по разные стороны от корня уравнения, если это не так, то заданный метод не может быть применен. В случае, когда функция касается одной точкой оси абсцисс, при этом знак ее не меняется, представленный метод нахождения корней нелинейных уравнений может быть применен, например, для функции y=x2 (рис. 1).
Рис. 1. Графическая интерпретация метода половинного деления
Пусть дано уравнение (x)=0, где (x)-непрерывная функция, и корень Р отделен на отрезке [a,b]. Требуется найти значение корня Р с точностью Е.
Суть алгоритма нахождения корня уравнения заданным методом можно представить совокупностью повторяющихся операций, называемых итерациями.
Алгоритм одной итерации можно представить в следующем виде:
Расчетная формула метода Ньютона-Рафсона получается из разложения функции (x) = 0 в ряд Тейлора в окрестности точки xn . При ограничении разложения двумя членами ряда получим
(x) = (xn) + (x-xn)'(xn) + O("(xn)) .
Здесь O (от английского order) означает порядок остаточного члена в разложении, который в дальнейшем считается малым.
Из соотношения (x) (xn) + (x - xn)'(xn) 0
получаем .
Обычно окончательная формула записывается в виде
.
Таким образом, зная какое-либо предыдущее приближение xn , где n-номер приближения или итерации (n 0), можно определить последующее приближенное значение корня xn+1. Если разность текущего и предыдущего значения аргумента по модулю меньше либо равно точности, | xn+1 – xn | , то значение xn+1 считается приближенным значением корня уравнения (x) = 0.
Кроме предыдущего условия окончания вычисления, можно использовать условие малости функций (x) около корня, т.е.
|(xn)| f или |(xn+1)| f, где f –заданная погрешность.
Рассмотрим геометрическое толкование метода касательных (рис.2), где значения корня Р определяется следующим образом.
Рис.2. Графическая интерпретация метода касательных
Исходя из некоторого начального приближения x0 , находим соответствующее ему значение (x0). Проводим касательную к кривой (x) через точку (x0) и ищем точку пересечения этой касательной с осью Х. Эта точка будет значением xn, так как требовалось провести через точку с координатами (x0, (x0)) прямую с угловым коэффициентом '(x0) и затем найти её пересечение с осью Х.
Величина отрезка |x0 - xn| больше заданной погрешности , поэтому поиск значения корня продолжается аналогично: зная только что найденное значение xn, которое принимается за исходное, определяем (xn) , '(xn) и xn+1 по той же формуле
xn+1 = xn , далее опять проверяется условие |xn+1 – xn| .
Подобное рассмотрение продолжается до тех пор, пока не выполнятся условия окончания поиска приближенного значения корня.
Этот метод лишь немного отличается от метода касательных и обладает меньшей скоростью сходимости. Здесь значение производной вычисляется всего один раз в точке первого приближения и больше не изменяется. Следовательно, её вычисление будет стоять до оператора цикла. Общая формула вычисления последующего приближения будет выглядеть так: xn+1 = xn .
Для выполнения лабораторной работы необходимо первоначально ознакомиться с теоретической частью. Затем выполнить два задания: вычисление суммы сходящегося ряда и нахождение корня уравнения заданным методом. Для каждого задания необходимо представить алгоритм решения задачи с помощью блок-схемы.
Для нахождения корня уравнения во втором задании необходимо первоначально проанализировать функцию с целью правильного задания исходных данных.
3.1. Примеры выполнения программ
Вычисление суммы сходящегося ряда с заданной точностью
Var {раздел объявления переменных}
n: integer; {переменная сходящегося ряда}
term, summa, precision: real; {переменные, означающие соответственно член ряда, сумма ряда, точность вычисления}
BEGIN {начало тела программы}
Writeln('Данная программа вычисляет сумму сходящегося ряда с за данной точностью, каждый член ряда вычисляется по формуле term=1/n'); {оператор вывода, который описывает назначение программы}
Writeln('Введите точность вычисления');
Readln(precision); {ожидание ввода с клавиатуры, введенное значение запишется в переменную precision}
summa:=0; {для того чтобы накапливать сумму в переменной summa, ее необходимо обнулить, так как при выделении памяти в ней может быть любое значение соответствующего типа}
n:=1; {присваиваем первоначальное значение до входа в цикл согласно заданию}
Repeat
term:=1/n; {вычисление текущего значения члена ряда}
summa:=summa+term; {накопление суммы, к предыдущему значению суммы прибавляется текущее значение}
n:=n+1; {к предыдущему значению переменной «n» прибавляем единицу согласно условию задачи}
Until term<=precision; {цикл выполняется до тех пор, пока текущее значение члена ряда не станет меньшим либо равным точности вычисления}
Writeln('Сумма сходящегося ряда с заданной точностью=', summa: 5: 2); {вывод результата с использованием форматирования}
Writeln('Количество членов ряда=', n);
END. {конец программы}
Пример программы, вычисляющей корень уравнения y=x2-5 методом половинного деления
Uses Crt; {подключаем модуль Crt для того, чтобы воспользоваться процедурой очистки экрана ClrScr;}
Var c, Fc, Fb: double;
a, b, e: real;
BEGIN
ClrScr; {очистка экрана}
Writeln(‘Данная программа находит корень уравнения методом половинного деления y=x2-5’);
Writeln(‘Введите значения концов отрезка, на котором имеется один корень, а также точность вычисления’);
Readln(a,b,e);
{цикл выполняется до тех пор, пока разность концов отрезка по модулю будет больше точности вычисления}
While (abs(b-a)>e) Do
Begin
if (keypressed) then halt; {данная строка обозначает, что при нажатии любой клавиши произойдет выход из программы, это нужно для избегания зацикливания, если начальные данные заданны не верно}
c:=(a+b)/2; {находим середину отрезка}
Fc:=sqr(c)-5; {вычисляем значение функции в новой точке “c”}
Fb:=sqr(b)-5; {вычисляем значение функции в точке “b”}
{если произведение значений функций в точках ‘c’ и ’b’ имеют разные знаки, то на этом промежутке находится корень уравнения}
if (Fc*Fb)>0 then b:=c else a:=c;
End; {окончание цикла while}
Writeln('Корень=', c: 6: 5); {вывод результата}
Readln; {задержка для просмотра результата}
END.
Пример программы, вычисляющей корень уравнения y=x2-5 методом касательных
Uses Crt;
Var F, F_, xLast, e, x: double;
BEGIN
ClrScr;
Writeln(‘Данная программа находит корень уравнения методом касательных y=x2-5’);
Writeln(‘Введите значение аргумента первоначального приближения’);
Readln(x);
Writeln(‘Введите значение точности’);
Readln(e);
Repeat
if (keypressed) then halt;
F:=x*x-5; {подсчет значения функции}
F_:=2*x; {подсчет значения производной функции}
xLast:=x; {сохранение предыдущего значения}
x:=xLast - F/F_; {подсчет текущего значения}
Until (abs(xLast-x)<e);
Writeln('Корень=', x: 5: 4);
Readln;
END.
4.1. Список заданий на вычисление суммы сходящегося ряда
В списке заданий (табл. 1) ряд может быть представлен как последовательностью членов ряда, так и в общем виде:
Таблица 1
|
№ вар-та |
Задание |
№ вар-та |
Задание |
|
1 |
16 |
||
|
2 |
17 |
||
|
3 |
18 |
||
|
4 |
19 |
||
|
5 |
20 |
||
|
6 |
21 |
||
|
7 |
22 |
||
|
8 |
23 |
||
|
9 |
24 |
||
|
10 |
25 |
||
|
11 |
26 |
||
|
12 |
27 |
||
|
13 |
28 |
Окончание табл. 1
|
№ вар-та |
Задание |
№ вар-та |
Задание |
|
14 |
29 |
||
|
15 |
30 |
Примечание: x, p – это константы, объявленные в программе.
4.2. Список заданий на нахождение корней уравнений
В списке заданий (табл. 2) используются следующие сокращения:
A – метод половинного деления
B – метод Ньютона-Рафсона (метод касательных)
C – модифицированный метод Ньютона (метод хорд)
Таблица 2
|
№ |
Уравнение |
Метод |
№ |
Уравнение |
Метод |
|
1 |
B |
16 |
A |
||
|
2 |
A |
17 |
B |
||
|
3 |
C |
18 |
B |
||
|
4 |
A |
19 |
A |
||
|
5 |
C |
20 |
C |
||
|
6 |
A |
21 |
B |
||
|
7 |
B |
22 |
C |
||
|
8 |
A |
23 |
A |
||
|
9 |
B |
24 |
B |
||
|
10 |
C |
25 |
C |
||
|
11 |
B |
26 |
C |
Окончание табл. 2
|
№ |
Уравнение |
Метод |
№ |
Уравнение |
Метод |
|
12 |
C |
27 |
A |
||
|
13 |
B |
28 |
C |
||
|
14 |
A |
29 |
B |
||
|
15 |
C |
30 |
A |
f(x0)
x 0
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Брянский государственный технический университет
b
xn+2
n+1
x n
0
f(x)
x
P
f(x)
a
c=b1
0
f(x)
x
P
f(x)
f(b)
f(a)