БИЛЕТ.Этапы решения прикладных задач. Машинное представление числа. Числа с плавающей точкой.
БИЛЕТ.Этапы решения прикладных задач. Машинное представление числа. Числа с плавающей точкой.
Процесс решения задачи с использованием ЭВМ включает, как правило, следующие этапы:
1. Математическая постановка задачи и построение математической модели.На данном этапе требуется
· определить, что дано, что надо получить;
· выделить наиболее существенные свойства изучаемого объекта;
· установить между ними количественные соотношения; Требования к математической модели:
· Математическая модель должна быть адекватной, т.е. правильно отражать действительность;
· Математическая модель не должна быть слишком сложной.
2. Алгоритмизация,т.е.
· Поиск метода решения задачи в рамках математической модели
· Разработка алгоритма (в виде словесного описания, математических формул, блок-схем).
3. Перевод алгоритма на язык программирования.
4. Исполнение программы на ЭВМ.В результате–получение результатоврешения.
5. Анализ полученных результатов.Полученные результаты сравниваются сожидаемыми, с данными, полученными экспериментальным путем.
Методы решения задачи делятся на | ||||
· | Точные: | · | Приближенные | |
аналитические | аналитические | |||
· | графические | · | графические | |
· | численные |
2БИЛЕТ.Структура полной погрешности эксперимента.
Погрешность возникает на ряде этапов решения задачи. Введем обозначения:
R –точное решение задачи(результат);
R – приближенное решение задачи;
ε – полная погрешность.
Полная погрешность e = R - R включает в себя:
· Погрешность исходных данных и математической модели.Возникает попричине неточности исходных данных и несоответствия построенной математической модели реальной ситуации. Таким образом, будет получен результат R1≠R.
e 1= R - R1
ε1–неустранимая погрешность.
· Погрешность метода.Возникает,если выбран приближенный(например,численный) метод. Таким образом, будет получен результат R2≠R1.
e 2= R1- R2
ε2 –устранимая погрешность.
· Погрешность вычислений:e3=R2-R3.
Таким образом, полная погрешность
БИЛЕТ.Методы, используемые для отделения корней уравнения с одной переменной
Отделение корней
II. Отделения корней программным способом.
Пусть имеется уравнение F(x)=0, причем все корни находятся на отрезке [a,b]. Будем вычислять все значения функции y=F(x), начиная с точки x=a, двигаясь вправо шагом h. Если функция на отрезке длины h меняет знак (т.е. F(a)F(b)<0) и монотонна, можно считать, что на этом отрезке ровно 1 корень.
Правильность нахождения отрезков, содержащих один корень, зависит от характера функции y=F(x) и от величины шага h. При выборе шага должна соблюдаться «золотая середина», т.к. шаг h должен быть с одной стороны достаточно малым, чтобы не произошло потери корней, а с другой стороны не настолько маленьким, чтобы число отрезков не было слишком большим.
Метод Гаусса.
Метод Гаусса относится к точным методам, однако вычислительная ошибка присутствует всегда (ошибка округления и, возможно, ошибка исходных данных). Рассмотрим систему m линейных уравнений с n неизвестными:
ìa | x | + | a | x | + | ... | + | a | x | = | b | |||||||||
ï 11 | + | + | + | 1n | n | = | ||||||||||||||
ïa21x1 | a22 x2 | ... | a2n xn | b2 | ||||||||||||||||
í...................... | ||||||||||||||||||||
ï | ||||||||||||||||||||
ïa | x | + | a | m2 | x | + | ... | + | a | mn | x | n | = | b | ||||||
î | m1 1 | n |
Алгоритм состоит из двух этапов.
I. Прямой ход – приведение матрицы к треугольному виду (сверху вниз):
ìx | + a¢ | x | + | ... | + | a¢ | x | n | = | b¢ | ||||||
ï | 1n | |||||||||||||||
ï | a¢ | x | + | ... | + | a¢ | x | n | = | b¢ | ||||||
2n | ||||||||||||||||
í...................... | ||||||||||||||||
ï | ||||||||||||||||
ï | xn | = | bn¢ | |||||||||||||
î |
II. Обратный ход–определение неизвестных(снизу вверх).
Ручные вычисления по схеме единственного деления оформляют в виде таблицы с контролем вычислений, для чего в таблицу включены
· столбец контрольных сумм S,
· столбец сточных сумм S.
Контроль в прямом ходе:
· После внесения коэффициентов при неизвестных и свободных членов исходной системы находят контрольные суммы (суммы коэффициентов и свободных членов по строкам) и вносят их в столбец S.
· Далее, выполняя преобразования, над контрольными суммами производятся те же преобразования, что и над свободными членами.
· После выполнения каждого преобразования находят строчную сумму результатов и помещают ее в столбец S.
· При отсутствии вычислительных ошибок числа в столбцах S и S должны практически совпадать.
Контроль в обратном ходе:
При безошибочном выполнении вычислений в столбце S должны быть на единицу больше соответствующих значений неизвестных из столбца свободных членов Рассмотрим примеры решения СЛУ методом Гаусса
Разделы | x1 | x2 | x3 | св чл | сумма | S | |
3,25 | 14,52 | -1,32 | 367,58 | 384,03 | |||
32,02 | -4,36 | 5,73 | 516,91 | 550,3 | |||
А | 7,21 | 11,92 | -41,46 | -886,32 | -908,65 | ||
4,4677 | -0,4062 | 113,1015 | 118,1631 | 118,163 | |||
-147,4158 | 18,7365 | -3104,6000 | -3233,2825 | -3233,2793 | |||
-20,2921 | -38,5313 | -1701,7818 | -1760,606 | -1760,6052 | |||
А1 | -0,1271 | 21,0602 | 21,9331 | 21,9331 | |||
-41,1104 | -1274,4261 | -1315,5373 | -1315,5365 | ||||
А2 | 31,0001 | 32,0001 | 32,0001 | ||||
31,0001 | 32,0001 | ||||||
В | 25,0003 | 26,0003 | |||||
13,9999 |
БИЛЕТ.Решение систем линейных алгебраических уравнений. Требования к сходимости итерационного процесса.
Первая половина в билете №9.
Функцию r(x,y), определяющую расстояние между точками x и y множества X назовем метрикой, если
1) r(x,y)³0
2) r(x,y)=0 x=y
3) r(x,y)= r(y,x)
4) r(x,y)£ r(x,z)+ r(z,y).
Множество X с введенной метрикой r назовем метрическим пространством. Последовательность точек метрического пространства называется фундаментальной,
если ("e > 0)($N )("m, n > N )[r(xm , xn ) < e].
Пространство называется полным, если в нем любая фундаментальная последовательность сходится.
Отображение F пространства E в себя называется сжимающим, если
($a, 0 < a <1)("x, y Ï E)[r(F(x), F( y)) £ a r(x, y)]
x – неподвижная точка, если F(x)=x.
Оценка расстояния между неподвижной точкой и приближением x(k) производится следующим образом:
r(x, x(k ))£ | a k | r(x(0), x(k ))или r(x, x(k ))£ | a | r(x(k -1) , x(k ) ). | |||
1 -a | 1 -a | ||||||
Таким образом, чтобы погрешность вычислений была меньше наперед заданного числа
ε, достаточно потребовать r(x(k -1) , x(k ) )£ e | 1 -a | . | |||||||
a | |||||||||
Рассмотрим 3 типа метрики. | |||||||||
Пусть x(x1,x2,…,xn) и y(y1,y2,…,yn) – две точки n-мерного пространства. | |||||||||
I. r1 (x, y) = max | xi | - yi | Максимальная из сумм модулей коэффициентов при неизвестных в | ||||||
1£i£n | |||||||||
правой | части | системы, взятых по | строкам, должна быть меньше единицы: | ||||||
n | |||||||||
a1 = max1£i£n | å aij <1 |
j=1
n
II. r21 (x, y) = å xi - yi Максимальная из сумм модулей коэффициентов при неизвестных
i=1
в | правой части | системы, | взятых | по столбцам, должна быть | меньше | единицы: | |||||||||
n | |||||||||||||||
a2 | = max1£j£n | å | aij | < 1 | |||||||||||
i=1 | |||||||||||||||
III. r3 (x, y) = | n | - yi )2Корень квадратный из суммы квадратов коэффициентов при | |||||||||||||
å(xi | |||||||||||||||
i=1 | |||||||||||||||
неизвестных | в | правой | части | системы, должен быть | меньше | единицы: | |||||||||
n | n | ||||||||||||||
a3=å åaij2¹1<1 | |||||||||||||||
i=1 | j =1 |
СЛУ преобразуется таким образом, чтобы по одной из метрик выполнялось α < 1.
ìx | = a | x | + | a | x | + | ... | + | a | x | + | b | ||||||||||||||
ï 1 | 1n | n | ||||||||||||||||||||||||
ïx2 | = a21x1 | + | a22 x2 | + | ... | + | a2n xn | + | b2 | |||||||||||||||||
í...................... | ||||||||||||||||||||||||||
ï | ||||||||||||||||||||||||||
ïx | n | = a | x | + | a | m2 | x | + | ... | + | a | mn | x | n | = | b | n | |||||||||
î | m1 1 |
При этом СЛУ задает отображение, которое при α < 1 будет сжимающим. Значит, взяв любую точку в качестве начального приближения, получим последовательность точек, которая будет сходиться к неподвижной точке; это точка и будет решением системы. Чтобы привести СЛУ к итерационному виду нужно:
1) с помощью равносильных преобразований привести систему к виду с преобладающими диагональными коэффициентами (по абсолютной величине);
2) разделить все уравнения на соответствующие диагональные коэффициенты и выразить из каждого уравнения неизвестное с коэффициентом, равным единице.
Если для этой системы α < 1, то система задает сжимающее отображение.
10БИЛЕТ.Оценка погрешности метода простой итерации. 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||;–критерий выхода.
БИЛЕТ.Метод Зейделя
При решении СЛУ методом простой итерации каждый шаг итерационного процесса состоит в переходе от уже имеющегося приближения значений неизвестных к новому приближению.
Основная идея метода Зейделя состоит в том, что на каждом шаге итерационного процесса при вычислении значений yi учитываются уже полученные значения y1, y2,…,yi-
1.
I. Условие α<1 является достаточным для сходимости итерационного процесса метода Зейделя. Причем метод Зейделя обеспечивает более быструю сходимость, чем метод простой итерации.
Рассмотрим решение системы трех линейных уравнений с тремя неизвестными методом Зейделя (взяв за основу метод итерации)
program slu_zejdel1;
{ *** с использованием евклидовой метрики *** } var p,b,x1,x2,x3,y1,y2,y3,a,e: real;
N: 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
Как видно из примера, по сравнению с методом итераций решение получено за меньшее количество шагов.
II. Рассмотрим практическую схему преобразования исходной СЛУ, гарантирующую сходимость метода Зейделя.
Пусть система записана в матричной форме: Ax=b.
Умножим левую и правую части слева на матрицу AT: ATAx= AT b.
Обозначим : ATA=C, AT b=d.
Преобразованная система станет иметь вид: Cx=d. Такую систему называют нормальной:
· матрица C является симметричной;
· все элементы главной диагонали матрицы C положительны. Нормальную систему легко привести к виду:
xi =åaij x j | + b j , | (i = 1,2,¼, n) , где ai = - | cij | ( j ¹ i) | и bi | = | di | . | ||||||||||||||
cii | ||||||||||||||||||||||
j ¹i | cii | |||||||||||||||||||||
Вычислительные формулы имеют вид: | ||||||||||||||||||||||
ì | n | |||||||||||||||||||||
ïy1 = åa1 j x j + b1 | ||||||||||||||||||||||
ï | j =1 | |||||||||||||||||||||
ï | n | |||||||||||||||||||||
ïy2 | = a21 y1 + åa2 j x j + b2 | |||||||||||||||||||||
ï | j =1 | |||||||||||||||||||||
ï | ||||||||||||||||||||||
ï... | ||||||||||||||||||||||
í | i-1 | n | ||||||||||||||||||||
ï | ||||||||||||||||||||||
=åaij y j +åaij x j + bi | ||||||||||||||||||||||
ïyi | ||||||||||||||||||||||
ï | j =1 | j =i | ||||||||||||||||||||
ï... | ||||||||||||||||||||||
ï | n-1 | |||||||||||||||||||||
ïyn =åanj y j + ann xn + bn | ||||||||||||||||||||||
î | ||||||||||||||||||||||
ï | j =1 | |||||||||||||||||||||
Рассмотрим на примере. | ||||||||||||||||||||||
æ 3,25 | 14,52 | -1,32 ö | æ | 367,58 | ö | æ 3,25 | 32,02 | 7,21 | ö | |||||||||||||
ç | - 4,36 | ÷ | ç | ÷ | ç | - 4,36 | ÷ | |||||||||||||||
A = ç | 32,02 | 5,73 | ÷ | b = ç | 516,91 | ÷ | AT = ç | 14,52 | 11,92 | ÷ | ||||||||||||
ç | 7,21 | 11,92 | - 41,46 | ÷ | ç | - 886,32 | ÷ | ç | -1,32 | 5,73 | - 41,46 | ÷ | ||||||||||
è | ø | è | ø | è | ø | |||||||||||||||||
æ | 1087,827 | - 6,474 | -119,742 ö | æ | 11355,726 ö | |||||||||||||||||
ç | - 6,474 | - 538,3524 | ÷ | D = | ç | - 7481,4004 | ÷ | |||||||||||||||
C = AT A = ç | 371,9264 | ÷ | AT b = ç | ÷ | ||||||||||||||||||
ç | -119,742 | - 538,3524 | 1753,5069 | ÷ | ç | 39223,5159 | ÷ | |||||||||||||||
è | ø | è | ø |
После деления на диагональные элементы получим:
æ | - 0,0060 | - 0,1101ö | æ | 10,4389 ö | ||||
ç | - 0,0174 | -1,4475 | ÷ | ç | ÷ | |||
a = ç | ÷ | b = ç | - 20,1153÷ | |||||
ç | - 0,0683 | - 0,3070 | ÷ | ç | 22,3686 | ÷ | ||
è | ø | è | ø |
Рассмотрим решение системы трех линейных уравнений с тремя неизвестными методом Зейделя (взяв в качестве метрики, используемой в программе, r1 (x, y) = max xi - yi ).
1£i£n
program slu_zejdel2;
var x1,y1,x2,y2,x3,y3,e,a,b,c: real;
N: integer;
begin
write('Введите X1, X2, X3 - '); readln(x1,x2,x3); write('Введите погрешность Е - '); readln(e); N:=0; {число итераций}
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
Решением
Дифференциального
Уравнения
(1)
(1) называется функция
y(x),
подстановка которой в уравнение обращает его в тождество: y¢(x) = f (x, y(x)) .
График решения y=y(x) называется интегральной кривой.
Задача Коши для дифференциального уравнения(1)состоит в том,чтобы найтирешение дифференциального уравнения (1), удовлетворяющее начальному условию y(x0)=y0 (2).Пару чисел (x0,y0) называют начальными данными.
Решение задачи Коши называется частным решением дифференциальногоуравнения (1)при условии(2).
Геометрически задача Коши означает, что требуется найти интегральную кривую y=y(x),проходящую через заданную точку (x0,y0).
Теоремао существовании и единственности решения задачи Коши.
Пусть функция f(x,y) – правая часть уравнения y¢ = f (x, y) - непрерывна вместе со
своей частной производной по переменной y | ¶f (x, y) | в некоторой области D на | |
dy | |||
плоскости. Тогда при любых начальных данных (x0,y0)ÎD задача Коши имеет единственное решение y=y(x).
При выполнении условий теоремы через точку (x0,y0) на плоскости проходит единственная интегральная кривая.
В классическом анализе разработано немало приемов решения дифференциальных уравнений, однако при решении практических задач эти методы не дают результата. В этом случае прибегают к методам приближенного решения дифференциальных уравнений. В зависимости от формы представления решения выделяют
· аналитические методы(решение в виде аналитического выражения);
· графические методы(решение в виде графика);
· численные методы(решение в виде таблицы).
Численное решение задачи Коши состоит в том, чтобы получить искомое решение y(x) в виде таблицы его приближенных значений аргумента x на некотором отрезке [a, b]:
x0=a, x1, x2, …, xm=b | (3) |
Точки (3) называют узловыми, множество этих точек называют сеткой наотрезке [a, b].
Как правило, используют равномерную сетку с шагом h: h = b m-a xi=x0+ih (i=0, 1, …, m)
Приближенные значения численного решения задачи Коши в узловых точках обозначим yi.
yi » y(xi),где(i=0, 1, …, m)
Начальное условие выполняется точно: y0 = y(x0).
Величина погрешности численного решения задачи Коши на сетке отрезка [a, b] оценивается величиной d = max{ yi - y(xi )},
1£i£m
т.е. расстоянием между векторами приближенного решения (y0, y1, …,ym) и точного решения (y(x0), y(x1), …,y(xm)) на сетке по m-норме.
{ y’=f(x, y); (1)
y(x0)=y0;
Решить обыкновенное диф. ур. – найти функ y=y(x), которая при подстановке даёт тождество.
Существование и единственность решения ур. (1) обеспечиваются теоремой. Теорема Пикара: если функ. f определена и непрерывна в некоторой области G,
определяемой неравенствами:
|x–x0|≤a,|y–y0|≤b,
и удовлетворяет в этой области условию Липшица по y:
|f(x, y1)–f(x, y2)|≤M|y1–y2|,
то на некотором отрезке |x–x0|≤h, где h – положительное число, существует, и при том только одно, решение y=y(x) уравнения (1), удовлетворяющее начальному условию
y0=y(x0).
M=max|f’y(x, y)|–константа Липшица.
Для нормальных систем ОДУ используются те же методы,только в векторной форме:
y’=f(x, y),гдеy=(y1(x),...,yn(x)); f(x, y)=(f1,...,fn);
Уравнения более высокого порядка принято сводить к системе:
Пусть:
y(n)=F(x, y(n-1),..., y);
Обозначим:
z1=y;
z2=y’;
………
zn=y(n-1);
Вместо ур. запишем систему с переменной z:
|z’1=z2;
|z’2=z3;
{………
|z’n-1=zn;
|z’n=F(x, zn,…, z1);
нормальная сист. диф. ур.
}