– полная погрешность.

Полная погрешность   R  R включает в себя:

• Погрешность исходных данных и математической модели. Возникает по причине неточности исходных данных и несоответствия построенной математической модели реальной ситуации. Таким образом, будет получен результат R₁≠R.

• ₁  R  R₁

ε₁ – неустранимая погрешность.

• Погрешность метода. Возникает, если выбран приближенный (например, численный) метод. Таким образом, будет получен результат R₂≠R₁.

• ₂  R₁  R₂

ε₂ – устранимая погрешность.

• Погрешность вычислений: ₃  R₂  R₃ .

Таким образом, полная погрешность

4. Методы, используемые для отделения корней уравнения с одной переменной

Отделение корней

I. Графический способ отделения корней

а) Теорема. Если на отрезке [a,b] функция y=F(x) определена и непрерывна, и на его концах принимает значения разных знаков (т.е. F(a)F(b)<0), то уравнение F(x)=0 имеет на этом отрезке, по крайней мере, один корень.

Если функция y=F(x) на отрезке [a,b] строго монотонна, то корень единственный.

Требуется указать отрезок, содержащий нуль функции.

Например, пусть требуется отделить корни уравнения x²-x-1=0. Построим график функции y=x²-x-1 и укажем отрезки, содержащие точки пересечения графика функции с осью абсцисс. Искомые промежутки: [-1; 0] [1; 2].

б) Иногда проще рассмотреть вместо уравнения y=F(x) равносильное ему уравнение f₁(x)=f₂(x). В этом случае требуется указать отрезок, содержащий абсциссу точки пересечения графиков функций y=f₁(x) и y=f₂(x).

Например, пусть требуется отделить корни уравнения x²-x-1=0. Рассмотрим равносильное ему уравнение x²=x+1. Тогда вместо отрезков, содержащих точки пересечения графика функции y=x²-x-1 с

осью абсцисс, можно указать отрезки, содержащие точки пересечения графиков функций f₁(x)=x² и f₂(x)=x+1.

Искомые промежутки: [-2; 0] [1; 3].

6

II. Отделения корней программным способом.

Пусть имеется уравнение F(x)=0, причем все корни находятся на отрезке [a,b]. Будем вычислять все значения функции y=F(x), начиная с точки x=a, двигаясь вправо шагом h. Если функция на отрезке длины h меняет знак (т.е. F(a)F(b)<0) и монотонна, можно считать, что на этом отрезке ровно 1 корень.

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

5. Уточнение корней методом половинного деления. Алгоритм, блок-схема.

Пусть1) функция y=F(x) определена и непрерывна на отрезке [a,b].

2. F(a)F(b)<0

Требуется найти корень на отрезке с точностью ε.

Разделим отрезок [a,b] пополам точкой c  ^{a }₂ ^b . Если F (c)  0 , то возможны два случая:

1. F(x) меняет знак на отрезке [a; c];

2. F(x) меняет знак на отрезке [c; b].

Выбираем тот отрезок, на котором функция меняет знак. Если F(x) меняет знак на отрезке [a; c], то b:=c; если F(x) меняет знак на отрезке [c; b], то a:=c. Условие окончания счета: b  a   .

Корень уравнения: x  ^{a }₂ ^b . Погрешность метода: dx  ^{b }₂ ^a .

Рассмотрим положительные и отрицательные стороны метода половинного деления.

• не требует дифференцируемости

функции

7

• устойчив к ошибкам округления

y

y=F(x)

c₂=a

O a c₁=b c₀=b b x

Число шагов при заданном ε можно оценить следующим образом: |ξ–x_k|<(b–a)/2^k+1; где x_k – это k-е приближение к корню.

• – точный корень.

|ξ–x_k|<(b–a)/2^k+1<ε 2^k+1>((b–a)/ε) k+1>log₂((b–a)/ε); k>log₂((b–a)/ε)–1.

Недостаток: метод трудоёмок.

Достоинство: абсолютно устойчив.

8

6. Уточнение корней методом простой итерации. Теорема, алгоритм геометрическая иллюстрация. Оценка погрешности метода.

Заменим уравнение F(x)=0 равносильным уравнением x = f(x). Теорема.

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

1. функция f(x) определена и дифференцируема на отрезке [a,b];

2) x  [a,b] f(x)  [a,b]

3. q x[a,b] |f’(x)|q<1

Тогда итерационная последовательность x_n=f(x_n-1) (n=1,2,...) сходится при любом начальном члене x₀[a,b].

Таким образом, наша задача: преобразовать уравнение F(x)=0 к виду x = f(x), удовлетворяющему условиям теоремы 1-3 (хотя итерационная последовательность может сходиться и при невыполнении некоторых условий).

• зависимости от вида функции сходимость может происходить ступеньками либо по спирали.

y

y=x

y

y=x

f(x2)

y=f(x)

y=f(x)

f(x1)

f(x0)

f(x1)

f(x2)

O

x0

x1

x2 x3

x

f(x0)

O

x0 x

x1 x3

x2

Оценка погрешности метода итераций

Пусть x_n – приближение к истинному значению x^* корня уравнения x=f(x).

Абсолютная ошибка x_n=|x^*-x_n|.

Для оценки погрешности n-го приближения используется формула x_n

Приняв за нулевое приближение x_n-1 и учитывая, что при 0<q<1 будет qⁿ<q, для оценки

Значение q можно получить как верхнюю грань модуля производной |f’(x)| при x[a,b].

Чем q меньше, тем быстрее сходится ряд.

окончания счета xn  xn1  ^{(1  q)}

q

Преобразование к итерационному виду

9

1. Универсальный способ приведения уравнения F(x)=0 к виду x=f(x).

2. Иногда удается преобразовать уравнение F(x)=0 к виду x=f(x) более простым способом, выразив x из уравнения.

10

7. Метод касательных(Ньютона). Сходимость метода, оценка погрешности, геометрическая интерпретация.

Пусть функция y=F(x) определена, непрерывна, монотонна и дифференцируема в некоторой окрестности корня.Требуется найти корень на отрезке с точностью ε.

На k^ой итерации проводится касательная к графику функции y=F(x) при x=c_k и ищется точка пересечения касательной с осью абсцисс. При этом достаточно задать начальное приближение c₀, а не указывать отрезок [a,b].

Уравнение касательной к графику функции y=F(x) в точке x0 имеет вид:

y  F(x0 )  F (x0 )(x  x0 ) . Пересечение с осью Ox находится из условия y=0, откуда

Таким образом, получим формулу для нахождения последовательности c₁, c₂… точек

Условие окончания счета: c_i1  c_i  

Корень уравнения: c_i+1.

y

y=F(x)

c1	c2	c0	x
O

var c,e,g: real;

N:integer;

function f(x: real):real;

begin

{записать, функцию в виде f:=[математическое выражение]}

f:=x*x*x-x+4;end;

function df(x: real):real;

begin {записать, производную функции f в виде

df:=[математическое выражение]} df:=3*x*x-1;end; begin

write('Введите начальное приближение - c: ');readln(c); write('Введите требуемую погрешность - e:'); readln(e);

N:=0;

repeat N:=N+1;

g:=c;

c:=c-f(c)/df(c);

until abs(g-c)<e;

writeln('Приближенное значение корня - Х = ',c); writeln('Число итераций - N = ',N); readln end.

11

8. Метод хорд. Сходимость метода, оценка погрешности, геометрическая интерпретация.

Пусть1) функция y=F(x) определена и непрерывна на отрезке [a,b].

2. F(a)F(b)<0

Требуется найти корень на отрезке с точностью ε.

В качестве приближений к корню принимаются значения c₀, c₁, c₂… точек пересечения

Точка c делит отрезок [a,b] на две части. Ту из них, на которой функция знака не меняет, отбрасываем (аналогично методу половинного деления).

• качестве условия окончания счета можно принять условия: c_i  c_i1   (Минаева)

F (c_i )   (Турчак).

Корень уравнения: c_i.

y y=F(x)

B

B₁

A

9. Решение систем линейных алгебраических уравнений. Прямые и итерационные методы решения. Метод Гаусса, алгоритм, блок схема.

Рассмотрим систему m линейных уравнений с n неизвестными:

Ее можно записать в матричном виде A x = B, где

Решить СЛУ – значит найти набор таких чисел

уравнения в верные равенства.

СЛУ совместна, если она имеет хотя бы одно решение.

СЛУ несовместна (противоречива), если она не имеет решения.

Совместная СЛУ определенна, если она имеет единственное решение и неопределенна, если более одного решения.

СЛУ имеет единственное решение, если ранг матрицы A равен рангу расширенной матрицы (A|b): rang(A) = rang(A|b).

СЛУ имеет единственное решение, если rang(A) = n и бесконечно много решений, если rang(A) < n.

Если матрица A – квадратная и det(A)0, то она называется невырожденной.

СЛУ с n неизвестными, имеющими невырожденную матрицу A, совместна и имеет единственное решение.

Единичной матрицей E называется квадратная матрица, у которой на главной диагонали стоят единицы, а на остальных местах – нули.

Обратной матрицей по отношению к матрице A называется такая матрица A^-1, что A A^-

¹=A^-1 A = E.

Матрица A^T, полученная перестановкой в матрице A строк со столбцами, называется транспонированной.

Квадратная матрица симметрична, если A=A^T.

Все численные методы решения СЛУ можно разделить на прямые, итерационные и вероятностные.

Прямые методы дают решение системы за конечное число арифметических операций.

Например, метод Крамера (метод определителей),

метод Гаусса (метод последовательного исключения неизвестных).

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

Например, метод простой итерации, метод Зейделя.

«Плюсы»

 Требуют мало места в памяти  Самоисправляющиеся методы

Вероятностные методы носят общее название – методы Монте-Карло.

велико, то где-то допущена ошибка, если  мало, то ошибка отсутствует.

Метод Гаусса.

Метод Гаусса относится к точным методам, однако вычислительная ошибка присутствует всегда (ошибка округления и, возможно, ошибка исходных данных). Рассмотрим систему m линейных уравнений с n неизвестными:

Алгоритм состоит из двух этапов.

I. Прямой ход – приведение матрицы к треугольному виду (сверху вниз):

14

35. Обратный ход – определение неизвестных (снизу вверх).

Ручные вычисления по схеме единственного деления оформляют в виде таблицы с контролем вычислений, для чего в таблицу включены

• столбец контрольных сумм ,

• столбец сточных сумм S.

Контроль в прямом ходе:

• После внесения коэффициентов при неизвестных и свободных членов исходной системы находят контрольные суммы (суммы коэффициентов и свободных членов по строкам) и вносят их в столбец .

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

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

• При отсутствии вычислительных ошибок числа в столбцах  и S должны практически совпадать.

Контроль в обратном ходе:

При безошибочном выполнении вычислений в столбце  должны быть на единицу больше соответствующих значений неизвестных из столбца свободных членов Рассмотрим примеры решения СЛУ методом Гаусса

15

10. Решение систем линейных алгебраических уравнений. Требования к сходимости итерационного процесса.

Первая половина в билете №9.

Функцию (x,y), определяющую расстояние между точками x и y множества X назовем метрикой, если

1. (x,y)0

2. (x,y)=0  x=y

3. (x,y)= (y,x)

4. (x,y) (x,z)+ (z,y).

Множество X с введенной метрикой  назовем метрическим пространством. Последовательность точек метрического пространства называется фундаментальной,

если   0N m, n  N (x_m , x_n )  .

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

Отображение F пространства E в себя называется сжимающим, если

, 0   1x, y  E(F(x), F( y))   (x, y)

10. – неподвижная точка, если F(x)=x.

Оценка расстояния между неподвижной точкой и приближением x^(k) производится следующим образом:

Таким образом, чтобы погрешность вычислений была меньше наперед заданного числа

10. 1

n

II. ₂₁ x, y   x_i  y_i Максимальная из сумм модулей коэффициентов при неизвестных

i1

СЛУ преобразуется таким образом, чтобы по одной из метрик выполнялось α < 1.

При этом СЛУ задает отображение, которое при α < 1 будет сжимающим. Значит, взяв любую точку в качестве начального приближения, получим последовательность точек, которая будет сходиться к неподвижной точке; это точка и будет решением системы. Чтобы привести СЛУ к итерационному виду нужно:

1) с помощью равносильных преобразований привести систему к виду с преобладающими диагональными коэффициентами (по абсолютной величине);

2) разделить все уравнения на соответствующие диагональные коэффициенты и выразить из каждого уравнения неизвестное с коэффициентом, равным единице.

Если для этой системы α < 1, то система задает сжимающее отображение.

11. Оценка погрешности метода простой итерации. x=Bx+d;

Пусть ||B||<1, имеем:

x*=Bx*+d;

_x(k)_=Bx(k-1)_+d;

x*=x^(k)+B(x*–x^(k-1));

Вычтем из каждой части x^(k-1):

_x*–x(k-1)_=x(k)_–x(k-1)_+B(x*–x(k-1)_);

||x*–x^(k-1)||≤

||x^(k)–x^(k-1)||+||B||•||x*–x^(k-1)||;

||x*–x^(k-1)||•(1–||B||)≤

||x^(k)–x^(k-1)||;

||x*–x^(k-1)||≤

||x^(k)–x^(k-1)||/(1–||B||);

Кроме того:

||x*–x^(k)||≤||B||•||x*–x^(k-1)||;

||x*–x^(k)||≤(||B||/(1–||B||))•||x^(k)–x^(k-1)||; (1) – Разность между точным решением и k-ым приближением.

Пусть требуется найти решение с точностью ε. Из (1) имеем:

(||B||/(1–||B||))•||x^(k)–x^(k-1)||<ε;

Достаточно выполнение условия:

||x^(k)–x^(k-1)||≤((1–||B||)•ε)/||B||; – критерий выхода.

17

12. Метод Зейделя

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

Основная идея метода Зейделя состоит в том, что на каждом шаге итерационного процесса при вычислении значений y_i учитываются уже полученные значения y₁, y₂,…,y_i-

1.

I. Условие α<1 является достаточным для сходимости итерационного процесса метода Зейделя. Причем метод Зейделя обеспечивает более быструю сходимость, чем метод простой итерации.

Рассмотрим решение системы трех линейных уравнений с тремя неизвестными методом Зейделя (взяв за основу метод итерации)

program slu_zejdel1;

{ *** с использованием евклидовой метрики *** } var p,b,x1,x2,x3,y1,y2,y3,a,e: real;

14. integer;

begin

write('Введите x1, x2, x3 : '); readln(x1,x2,x3);

write('Введите A, E : '); readln(a,e);

b:=e*(1-a)/a;

N:=0; {число итераций}

repeat

N:=N+1;

y1:= 0.1362*x2-0.1790*x3+16.1433;

y2:=-0.2238*y1+0.0909*x3+25.3154;

y3:= 0.1739*y1+0.2875*y2+21.3777;

p:=sqrt(sqr(x1-y1)+sqr(x2-y2)+sqr(x3-y3));

x1:=y1; x2:=y2; x3:=y3;

until p<=b;

writeln('x1 = ',x1:8:6);

writeln('x2 = ',x2:8:6);

writeln('x3 = ',x3:8:6);

writeln('Число итераций - N = ',N);

readln

end.

Введите x1, x2, x3 : 0 0 0

Введите A, E : 0.2218 0.0001

x1 = 13.999370

x2 = 25.000219

x3 = 30.999753

Число итераций - N=6

Как видно из примера, по сравнению с методом итераций решение получено за меньшее количество шагов.

18

II. Рассмотрим практическую схему преобразования исходной СЛУ, гарантирующую сходимость метода Зейделя.

Пусть система записана в матричной форме: Ax=b.

Умножим левую и правую части слева на матрицу A^T: A^TAx= A^T b.

Обозначим : A^TA=C, A^T b=d.

Преобразованная система станет иметь вид: Cx=d. Такую систему называют нормальной:

• матрица C является симметричной;

• все элементы главной диагонали матрицы C положительны. Нормальную систему легко привести к виду:

После деления на диагональные элементы получим:

Рассмотрим решение системы трех линейных уравнений с тремя неизвестными методом Зейделя (взяв в качестве метрики, используемой в программе, 1 x, y  max xi  yi ).

1in

program slu_zejdel2;

var x1,y1,x2,y2,x3,y3,e,a,b,c: real;

14. integer;

begin

write('Введите X1, X2, X3 - '); readln(x1,x2,x3); write('Введите погрешность Е - '); readln(e); N:=0; {число итераций}

19

repeat

N:=N+1;

y1:= 0.0060*x2+0.1101*x3+10.4389;

y2:= 0.0174*y1+1.4475*x3-20.1153;

y3:= 0.0683*y1+0.3070*y2+22.3686;

a:=abs(y1-x1); b:=abs(y2-x2); c:=abs(y3-x3);

if a<b then a:=b;

if a<c then a:=c;

x1:=y1; x2:=y2; x3:=y3;

until a<=e;

writeln('X1 = ',x1:11:8);

writeln('X2 = ',x2:11:8);

writeln('X3 = ',x3:11:8);

writeln('Число итераций - N = ',N);

readln

end.

Введите X1, X2, X3 - 0 0 0

Введите погрешность Е - .0001

X1 = 14.00204110

X2 = 25.00128107

X3 = 31.00033269

Число итераций - N = 18

20

13. Постановка задачи интерполирования. Параболическая интерполяция. Единственность задачи интерполирования многочленами.

Пусть известны значения функции f в некоторых точках:

Требуется получить y=f(x) для x[x₀,x_n], где xx_i. При этом аналитическое выражение а) не пригодно для вычислений либо б) неизвестно.

В этом случае строим приближающую функцию F(x)  f(x), такую что F(x) = f(x) при

(интерполированием), точки x₀, x₁, …, x_n узлами интерполяции.

Будим искать функцию F(x) в виде многочлена степени n:

P_n(x) = a₀ xⁿ + a₁ x^n-1 + … + a_n-1 x + a_n

Этот многочлен имеет n+1 коэффициент. Наложим на него n+1 условий (2). Таким образом можно однозначно определить коэффициенты многочлена.

Рассмотрим получившуюся систему уравнений: a_k x_k^nk  y_i (i  0, 1, ..., n) .

Ее определитель (определитель Вандермонда) отличен от нуля:

Значит, интерполяционный многочлен P_n(x) для функции f, заданной таблично,

существует и единственный. При этом какие-то коэффициенты могут равняться нулю (в том числе и a₀); следовательно, интерполяционный многочлен имеет степень не

большую, чем n.

Рассмотрим набор точек (x_i; y_i) i=0,1,…,n задающих некоторую таблицу – таблицу данных.

Формулировка задачи: для (n+1) точек заданы значения x₀, x₁,…, x_n соответствующие некоторой функции. y₀=f(x₀); y₁=f(x₁); …; y_n=f(x_n) функция неизвестна, и задана таблично. Требуется подобрать такую функ. φ(x), чтобы: