Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Топ:
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2017-06-20 | 436 |
5.00
из
|
Заказать работу |
|
|
Рассмотрим систему m линейных уравнений с n неизвестными:
ì a | x | + | a | x | + | ... | + | a | x | = | b | |||||||||
ï 11 | + | + | + | 1 n | n | = | ||||||||||||||
ï a 21 x 1 | a 22 x 2 | ... | a 2 n xn | b 2 | ||||||||||||||||
í...................... | ||||||||||||||||||||
ï | ||||||||||||||||||||
ï a | x | + | a | m 2 | x | + | ... | + | a | mn | x | n | = | b | ||||||
î | m 1 1 |
Ее можно записать в матричном виде A x = B, где
æ a | a | ... | a | ö | æ b | ö | æ | x | ö | |||
ç | 1 n ÷ | ç | ÷ | ç | ÷ | |||||||
ç a 21 | a 22 | ... | a 2 n ÷ | ç b 2 | ÷ | ç x 2 | ÷ | |||||
A =ç | ... | ÷ | b =ç | ... | ÷ | x =ç | ... | ÷ | ||||
ç | ÷ | ç | ÷ | ç | ÷ | |||||||
ç | am 2 | ÷ | ç | ÷ | ç | ÷ | ||||||
è am 1 | amn ø | è bm | ø | è xm ø |
Решить СЛУ –значит найти набор таких чисел
уравнения в верные равенства.
СЛУ совместна, если она имеет хотя бы одно решение.
СЛУ несовместна (противоречива), если она не имеет решения.
Совместная СЛУ определенна, если она имеет единственное решение и неопределенна, если более одного решения.
СЛУ имеет единственное решение, если ранг матрицы 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 -
1= A -1 A = E.
Матрица AT, полученная перестановкой в матрице A строк со столбцами, называется транспонированной.
Квадратная матрица симметрична, если A=AT.
Все численные методы решения СЛУ можно разделить на прямые, итерационные и вероятностные.
Прямые методы дают решение системы за конечное число арифметических операций.
Например, метод Крамера (метод определителей),
метод Гаусса (метод последовательного исключения неизвестных).
«Плюсы» | «Минусы» | |
· | Просты | · Достаточно громоздкие вычисления |
· | Универсальны | |
· Не требуют приведения к | ||
определенному виду |
Итерационные методы дают решение системы как предел последовательностиприближений, вычисляемых по единообразной схеме.
Например, метод простой итерации, метод Зейделя.
«Плюсы»
· Требуют мало места в памяти · Самоисправляющиеся методы
Вероятностные методы носят общее название–методы Монте-Карло.
Пусть получено решение СЛУ: | ~ | . Рассматривается вектор невязки | ~ | . Если | |||||||
e | |||||||||||
x | e = b - Ax |
велико, то где-то допущена ошибка, если e мало, то ошибка отсутствует.
Метод Гаусса.
Метод Гаусса относится к точным методам, однако вычислительная ошибка присутствует всегда (ошибка округления и, возможно, ошибка исходных данных). Рассмотрим систему m линейных уравнений с n неизвестными:
ì a | x | + | a | x | + | ... | + | a | x | = | b | |||||||||
ï 11 | + | + | + | 1 n | n | = | ||||||||||||||
ï a 21 x 1 | a 22 x 2 | ... | a 2 n xn | b 2 | ||||||||||||||||
í...................... | ||||||||||||||||||||
ï | ||||||||||||||||||||
ï a | x | + | a | m 2 | x | + | ... | + | a | mn | x | n | = | b | ||||||
î | m 1 1 | n |
Алгоритм состоит из двух этапов.
|
I. Прямой ход – приведение матрицы к треугольному виду (сверху вниз):
ì x | + a ¢ | x | + | ... | + | a ¢ | x | n | = | b ¢ | ||||||
ï | 1 n | |||||||||||||||
ï | a ¢ | x | + | ... | + | a ¢ | x | n | = | b ¢ | ||||||
2 n | ||||||||||||||||
í...................... | ||||||||||||||||
ï | ||||||||||||||||
ï | 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. r 1 (x, y) = max | xi | - yi | Максимальная из сумм модулей коэффициентов при неизвестных в | ||||||
1£ i £ n | |||||||||
правой | части | системы, взятых по | строкам, должна быть меньше единицы: | ||||||
n | |||||||||
a 1 = max1£ i £ n | å aij <1 |
|
j =1
n
II. r 21 (x, y) = å xi - yi Максимальная из сумм модулей коэффициентов при неизвестных
i =1
в | правой части | системы, | взятых | по столбцам, должна быть | меньше | единицы: | |||||||||
n | |||||||||||||||
a 2 | = max1£ j £ n | å | aij | < 1 | |||||||||||
i =1 | |||||||||||||||
III. r 3 (x, y) = | n | - yi)2Корень квадратный из суммы квадратов коэффициентов при | |||||||||||||
å(xi | |||||||||||||||
i =1 | |||||||||||||||
неизвестных | в | правой | части | системы, должен быть | меньше | единицы: | |||||||||
n | n | ||||||||||||||
a 3=å å aij 2¹1<1 | |||||||||||||||
i =1 | j =1 |
СЛУ преобразуется таким образом, чтобы по одной из метрик выполнялось α < 1.
ì x | = a | x | + | a | x | + | ... | + | a | x | + | b | ||||||||||||||
ï 1 | 1 n | n | ||||||||||||||||||||||||
ï x 2 | = a 21 x 1 | + | a 22 x 2 | + | ... | + | a 2 n xn | + | b 2 | |||||||||||||||||
í...................... | ||||||||||||||||||||||||||
ï | ||||||||||||||||||||||||||
ï x | n | = a | x | + | a | m 2 | x | + | ... | + | a | mn | x | n | = | b | n | |||||||||
î | m 1 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 | |||||||||||||||||||||
ï y 1 = å a 1 j x j + b 1 | ||||||||||||||||||||||
ï | j =1 | |||||||||||||||||||||
ï | n | |||||||||||||||||||||
ï y 2 | = a 21 y 1 + å a 2 j x j + b 2 | |||||||||||||||||||||
ï | 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 | ÷ | ||
è | ø | è | ø |
Рассмотрим решение системы трех линейных уравнений с тремя неизвестными методом Зейделя (взяв в качестве метрики, используемой в программе, r 1 (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
|
|
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!