Методичка Программирование

12)функция (1 x) 3 ;

14)функция (1 x) 2 ; S 1 2 x 3 x2 4 x3 5 x4 ...;

15)функция (1 x)m ;

17)число e; S 1 1 1 1 1 ...;

2! 3! 4!

Вычислить с заданной точностью ε сумму бесконечного ряда S, используя сторонние программы, например Mathsoft MathCAD, проверить правильность вычислений:

10N

22)S N 1 N! ;

N!

23)S N 1 (2N)!;

24)S N! e N ;

N 1

25)S 10 N (N 1)!.

N 1

Задание к лабораторной работе № 4

1. Одноклеточная амёба каждые три часа делится на две клетки. Сколько клеток будет через 3, 6, 9, ..., 24 часа? Через сколько часов количество клеток превысит 10 000? Начальное количество амёб вводится пользователем.

51

2.Начав тренировки, спортсмен в первый день пробежал 10 км. Каждый день он увеличивал норму на 10% от нормы предыдущего дня. Сколько км пробежал спортсмен во 2, 3, 4, ..., m-й день? Через сколько дней он будет пробегать более 25 км?

3.В течение месяца каждый день курс доллара падал. В первый день он составил а рублей. В каждый следующий на 3% и ещё на 0,1 руб. Каким будет курс доллара во 2, 3, 4, ..., n-й день? Через сколько дней он будет ниже b рублей?

4.Вес пациента до лечебного голодания составил 100 кг. В процессе голодания он каждые два дня терял в весе 1% от предыдущего значения. Через сколько дней вес пациента будет ниже 80 кг?

5.Каждый месяц коммерсант увеличивает цену товара на 1%. Через сколько месяцев цена товара увеличится более чем в два раза, если первоначальная цена равна а рублей?

6.Каждые 18 месяцев производительность процессора удваивается, а скорость работы оперативной памяти за год увеличивается на 10%. Через сколько лет скорость памяти удвоится относительно начального значения? Как изменится соотношение производительности процессора и скорости работы памяти за это время?

7.Ежемесячный процент дохода в банке составляет 1,6%. Через сколько месяцев, ваша сумма денег удвоится, если первоначально вы положили а рублей и каждый месяц ещё кладете по b рублей?

8.Изучая английский язык, студент каждый день учит столько слов, сколько за два предыдущих дня. Сколько слов он выучит в 3, 4, 5, ..., n-й день, если в первый и во второй день он выучил по 7 слов? Терпение студента иссякнет, когда за день ему придется выучить более 300 слов. Когда это произойдет, и сколько слов он выучит до этого времени?

9.В колбе n бактерий. В какой-то момент времени в колбу попадает вирус. В первую минуту он уничтожает одну бактерию, после чего вирус делится, а бактерии делятся каждые 2 минуты. В каждую следующую минуту вирусы уничтожают по одной бактерии и снова делятся. Через сколько минут вирусы уничтожат все бактерии?

10.Изучая английский язык, студент каждый день учит столько слов, сколько за два предыдущих дня и еще 3 слова дополнительно. Каждые 10 дней студент забывает 5 % выученных слов. Через сколько дней студент будет знать более 1500 слов, если в первый и во второй день он выучил по 6 слов?

Тема № 5. Численные методы

Решение уравнений численными методами

Пусть задана функция f (x). Требуется найти действительные корни (или один из корней) уравнения f (x) 0. Основными способами решения уравнение

f(x) 0 могут быть:

1)аналитическое (точное, в виде формулы);

52

2)приближенное (неточное):

-графический метод;

-численные методы.

Основная идея численных методов заключается в итерационном уточнении решения с помощью некоторого алгоритма.

Основными достоинствами численных методов является:

можно найти решение любого уравнения (если оно существует);

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

Кнедостаткам численных методов можно отнести:

невозможность найти точное значение;

невозможно исследовать поведение решения при изменении параметров;

большой объем вычислений;

в некоторых случаях сложно оценить ошибку;

нет универсальных методов.

В общем случае при решении уравнения численными методами задача разбивается на два этапа:

1)локализация корней;

2)вычисление корней с требуемой точностью.

Локализация является предметом математического анализа. Целью локализации является определение примерного местонахождения корней уравнения. ЭВМ может быть использована для построения графика f (x) на интервале или таблицы значений. При решении реальных задач отрезок локализации [a,b] часто известен из практики. Задача формализуется следующим образом: вычислить с заданной точностью ε корень уравнения f (x) 0, принадлежащий отрезку локализации [a,b]. Точность решения ε здесь может быть определена, как:

| x x* | ε, где x – точное, а x* – вычисленное значение корня.

Метод дихотомии (деления пополам)

Метод тривиален, поэтому приведем только алгоритм:

1)найти середину отрезка [a,b]: c (a b)/2;

2)если f (c) f (a) 0, то сдвинуть правую границу отрезка в середину отрезка;

3)если f (c) f (a) 0, то сдвинуть левую границу отрезка в середину отрезка;

4)повторять шаги 1-3, пока |b a| ε.

Основные достоинства алгоритма:

простота;

можно получить решение с заданной точностью (в пределах

точности машинных вычислений). Недостатки:

53

необходимо знать интервал;

на интервале [a,b] должно быть только одно решение;

метод применим только для функций одной переменной;

низкая скорость сходимости.

Метод простой итерации

Представим уравнение

f (x) 0

в виде

x y(x).

Искомый корень при подстановке обращает уравнение в тождество. Последовательность

x(n) y(x(n 1))

сходится к корню уравнения x при условии y'(x) q,

где 0 q 1, с линейной скоростью

x(n) x q x(n 1) x .

Из этого можно вывести, что

Отдельно возникает задача приведения уравнения к виду, удобному для итераций. Очевидно, что

f (x) 0 f (x) 0 .

Запишем уравнение в виде

x x f (x).

Параметр α подбирается из условия y'(x) q

или

1 f '(x) q.

54

Пусть f '(x)на отрезке a,b непрерывна и положительна. Тогда существуют такие m и M , что

0 m f '(x) M, x a,b .

Для выполнения условия

1 f '(x) 1

Достаточно, чтобы

0;2/M .

Если известны обе величины, то оптимальное

2 ,

M m

тогда

Метод Ньютона

Задавшись начальным приближением x0 [a,b], линерализуем функцию (рис. 11) в окрестностях точкиx0 , представив ее в виде отрезка ряда Тейлора:

f(x) f (x0) f '(x0) (x x0),

ибудем решать линейное относительно x уравнение

f (x1)

x*

0

Рис. 11. Уточнение корня уравнения методом Ньютона

Получим приближение к искомому корню

55

Критерий окончания счета| xk xk 1 | .

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

Образец выполнения задания № 1

Задание

Найти корень уравнения

x 3x 2,5 0

с точностью =10-4. Корень уравнения считать локализованным на отрезке [0, 2], для решения использовать метод простой итерации. На экран вывести вычисленное значение корня и для сравнения точное значение корня (x = 1,3853). Значения X0 – примерное начальное значение корня и – точность нахождения корня – вводятся с клавиатуры. В программе предусмотреть подсчет и вывод на экран числа итераций, за которое удается найти значение корня с заданной точностью.

Описание метода решения

Пусть уравнение

x 3x 2,5 0

имеет один корень на отрезке [a;b]. Функция F(x) непрерывна на отрезке [a; b]. Метод простой итерации заключается в замене уравнения

x 3x 2,5 0

эквивалентным ему уравнением вида

x 2,5 3x .

По этой формуле строится итерационный процесс. Поскольку y(x) 2,5 3x ,

имеем

корня уравнения сводится к последовательному вычислению чисел

56

хn = f(xn-1), n = 1, 2, 3… .

Процесс будем продолжать до тех пор, пока

xn 1 xn 1 0,333ε 2ε, 0,333

где – заданная абсолютная погрешность корня х.

Текст программы (результат работы на рис. 12)

function fun(x:real):real; begin

Result:=2.5-power(x,1/3); end;

var x0,x1,a,b,e,q:real;iterz:integer; begin

write(Rus('Введите приближенное значение X=')); readln(x1);

write(Rus('Введите точность e=')); readln(e);

write(Rus('Введите границы локализации A='):30); readln(a);

write(Rus('B='):30); readln(b);

{Анализ задачи} a:=abs((fun(a+0.0001)-fun(a))/0.0001); //y` в точке A b:=abs((fun(b+0.0001)-fun(b))/0.0001); //y` в точке B q:= max(a,b);

q:=(1-q)/q; if (q<=1) then

begin iterz:=0; repeat

iterz:=iterz+1;

x0:=x1;

x1:=fun(x0);

until (abs(x1-x0)<=abs(q*e));

writeln(Rus('Решение уравнения:')); writeln(Rus('Точное значение корня:'),1.3853:0:4); writeln(Rus('Вычисленное значение корня:'),x1:0:4); writeln(Rus('Число итераций:'),iterz);

end else

begin

writeln(Rus('Метод расходится!')); end;

57

end.

Рис. 12. Вычисление корня уравнения методом простой итерации

Примечание. Условие q 1 является достаточным (но не необходимым) условием сходимости. В некоторых случаях при заданном отрезке, содержащем корень, достаточное условие может не выполняться, и программа выдаст сообщение «метод расходится». Тогда нужно подобрать отрезок локализации таким образом, чтобы выполнялось условие q 1, или подобрать соответствующим образом значение α в формулах на стр. 54-55 и использовать его в функции fun (см. листинг).

Образец выполнения задания № 2

Задание

Найти корень уравнения

x 3x 2,5 0

с точностью =10-4. Корень уравнения считать локализованным на отрезке [0, 2]. Для решения использовать метод Ньютона. На экран вывести вычисленное значение корня и для сравнения точное значение корня (Х = 1,3853). Значения X0 (примерное значение корня) и (точность нахождения корня) вводятся с клавиатуры. В программе предусмотреть подсчет и вывод на экран числа итераций, за которое удается найти значение корня с заданной точностью.

Описание метода решения

Пусть уравнение

x 3x 2,5 0

имеет один корень на отрезке [a;b]. Функция

f x x 3x 2,5

непрерывна на отрезке [a; b], ее производная

f x 1 1 .

33 x2

58

Вычисления будем продолжать до тех пор, пока не будет выполнено условие

x(n 1) x(n) ε.

Чтобы не вычислять производную аналитически, воспользуемся

формулой численного дифференцирования: df (x) f (x x) f (x) . dx x

Текст программы (результат работы программы показан на рис. 13)

function fun(x:real):real; begin

Result:= x - 2.5 + power(x,1/3); end;

var x0,x1,e,q:real;iterz:integer; begin

write(Rus('Введите приближенное значение X=')); readln(x1);

write(Rus('Введите точность e=')); readln(e);

iterz:=0; repeat

iterz:=iterz+1;

x0:=x1;

q:=(fun(x0+0.0001)-fun(x0))/0.0001; // f' в точке x0

Рис. 13. Вычисление корня уравнения методом Ньютона

Образец выполнения задания № 3

Задание

59

Найти корень уравнения

x 3x 2,5 0

с точностью =10-4. Корень уравнения считать локализованным на отрезке [1, 2]. Для решения использовать метод бисекции (половинного деления). На экран вывести вычисленное значение корня и для сравнения - точное значение корня (x = 1,3853). Значения – точность нахождения корня, необходимо ввести с клавиатуры. В программе предусмотреть подсчет и вывод на экран числа итераций, за которое удается найти значение корня с заданной точностью.

Описание метода решения

Пусть уравнение

x 3x 2,5 0

имеет один корень на отрезке [a;b]. Функция F(x) непрерывна на отрезке [a; b]. Метод половинного деления заключается в следующем: сначала выбираем начальное приближение, деля отрезок пополам, т.е.

х0 = (a+b)/2.

Если F(x) = 0, то x0 является корнем уравнения. Если F(x) 0, то выбираем тот из отрезков, на концах которого функция имеет противоположные знаки. Полученный отрезок снова делим пополам и выполняем действия сначала и т.д. Процесс деления отрезка продолжаем до тех пор, пока длина отрезка, на концах которого функция имеет противоположные знаки, не будет меньше заданной погрешности .

Текст программы (результат работы на рис. 14)

function fun(x:real):real; begin

Result:= x - 2.5 + power(x,1/3); end;

var x0,x1,a,b,e:real;iterz:integer; begin

write(Rus('Введите точность e=')); readln(e);

write(Rus('Введите границы локализации A='):30); readln(a);

write(Rus('B='):30); readln(b); iterz:=0;

if (fun(a)*fun(b)<=0) then begin

repeat x1:=(a+b)/2; iterz:=iterz+1; x0:=x1;

60