Метод квадратичной интерполяции. Метод квадратичной интерполяции основан на применении одноименного метода

Метод квадратичной интерполяции основан на применении одноименного метода одномерной минимизации на этапе спуска по одной из выбранных координат.

Лекция 12. Численные методы решения систем уравнений

12.1. Системы линейных алгебраических уравнений 12.1.1. Основные понятия Рассмотрим следующую систему линейных алгебраических уравнений a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2.................................................. an1x1 + an2x2 + … + annxn = bn В матричной форме эта система быть записана в виде AX=B где А - матрица системы, X - искомый вектор, B - заданный вектор:   В компонентной форме система может быть записана в виде   или, короче где i,j=1,2,...,n. Компоненты вектора X обозначаются xi - представляют собой одномерный массив Компоненты вектора B обозначаются bi - представляют собой одномерный массив Другая форма записи векторов X=(x1,x2,...,xn)^T B=(b1,b2,...,bn)^T Компоненты матрицы А обозначаются aij - представляют собой двумерный массив, причем первый индекс - номер строки, второй индекс - номер столбца. Компоненты a11, a22, …,ann лежат на главной диагонали матрицы А. Компоненты an1, an-1,2, …,a1n лежат на побочной диагонали матрицы А. Скалярным произведением двух векторов C=(c1,c2,...,cn)^T и D=(d1,d2,...,dn)^T называется число, равное C·D=c1d1+c2d2+... + cndn Пример. Скалярное произведение первого столбца матрицы А на ее вторую строку:

12.1.2. Формулы Крамера Решение системы трех уравнений a11x1 + a12x2 + a13xn = b1 a21x1 + a22x2 + a23xn = b2 a31x1 + an2x2 + a33xn = b3 может быть найдено по формулам Крамера: x1=Δ1/Δ x2=Δ2/Δ x3=Δ3/Δ где Пример программы cls rem ИСХОДНЫЕ ДАННЫЕ a11=1:a12=2:a13=3:b1=6 a21=2:a22=1:a23=-1:b2=2 a31=3:a32=2:a33=3:b3=8 rem Решение системы трех линейных уравнений delt=a11*a22*a33+a12*a23*a31+a13*a21*a32  delta=delt-a13*a22*a31-a12*a21*a33-a11*a32*a23 delt1=b1*a22*a33+a12*a23*b3+a13*b2*a32 delta1=delt1-a13*a22*b3-a23*a32*b1-b2*a12*a33 delt2=a11*b2*a33+b1*a23*a31+a13*b3*a21 delta2=delt2-a13*b2*a31-a23*b3*a11-a33*a21*b1 delt3=a11*a22*b3+a12*b2*a31+b1*a21*a32   delta3=delt3-b1*a22*a31-b2*a32*a11-b3*a21*a12 x1=delta1/delta  x2=delta2/delta x3=delta3/delta ? x1,x2,x3 end

12.1.3. Метод Гаусса Суть метода Гаусса состоит в том, что с помощью некоторых операций исходную систему уравнений можно свести к более простой системе. Эта простая система имеет треугольный вид: a11x1 + a12x2 + a13x3 + ... a1NxN = b1   a22x2 + a23x3 + ... a2NxN = b2     a33x3 + ... a3NxN = b3 ...               ... aNNxN = bN Особенность этой системы - в строках с номером i все коэффициенты aij при j<i равны нулю. Если мы смогли привести нашу систему уравнений к такому треугольному виду, то решить уравнения уже просто. Из последнего уравнения находим xN= bN / aNN. Дальше подставляем его в предпоследнее уравнение и находим из него xN-1. Подставляем оба найденных решения в следующее с конца уравнение и находим xN-2. И так далее, пока не найдем x1, на чем решение заканчивается. Такая процедура называется обратной прогонкой. Теперь перейдем к вопросу как же добиться того, чтобы система стала треугольной. Из линейной алгебры (см. например, Крутицкая Н.И., Тихонравов А.В., Шишкин А.А., Аналитическая геометрия и линейная алгебра с приложениями) известно что если к некоторой строке системы уравнений прибавить любую линейную комбинацию любых других строк этой системы, то решение системы не изменится. Под линейной комбинацией строк понимается сумма строк, каждая из которых у множается на некоторое число (в принципе, любое). Нужно, чтобы во второй строке получилось уравнение, в которой отсутствует член при x1. Прибавим к этой строке первую строку, умноженную на некоторое число M. (a11x1 + a12x2 + a13x3 +... a1NxN = b1)*M + a21x1 + a22x2 + a23x3 +... a2NxN = b2 Получим (a11*М + a21) x1 +... = b1*M + b2 Для того, чтобы член при x1 равнялся нулю, нужно, чтобы M = - a21 / a11. Проделав эту операцию, получившееся уравнение запишем вместо второго и приступим к третьему уравнению. К нему мы прибавим первое уравнение, умноженное на M = - a31 / a11 и тоже получим ноль вместо члена при x1. Такую операцию нужно проделать над всеми остальными уравнениями. В результате получим систему такого вида: a11x1 + a12x2 + a13x3 + ... a1NxN = b1   a22x2 + a23x3 + ... a2NxN = b2   a32x2 + a33x3 + ... a3NxN = b3 ...           aN2x2 + aN3x3 + ... aNNxN = bN После этого будем избавляться от членов при x2 в третьем, четвертом, N-ом уравнении. Для этого нужно к уравнению с j-м номером прибавить 2-ое уравнение, умноженное на M = - aj2 / a22. Проделав эту операцию над всеми остальными уравнениями, получим систему где нет членов с x2 в уравнениях с номером больше 2. И так далее... Проделав это для третьего члена, четвертого... до тех пор, пока не кончатся уравнения, получим в итоге систему треугольного вида. Один из основных недостатков метода Гаусса связан с тем, что при его реализации накапливается вычислительная погрешность. Для того, чтобы уменьшить рост вычислительной погрешности применяются различные модификации метода Гаусса. Например, метод Гаусса с выбором главного элемента по столбцам, в этом случае на каждом этапе прямого хода строки матрицы переставляются таким образом, чтобы диагональный угловой элемент был максимальным. При исключении соответствующего неизвестного из других строк деление будет производиться на наибольший из возможных коэффициентов и следовательно относительная погрешность будет наименьшей. Существует метод Гаусса с выбором главного элемента по всей матрице. В этом случае переставляются не только строки, но и столбцы. Использование модификаций метода Гаусса приводит к усложнению алгоритма увеличению числа операций и соответственно к росту времени счета. Поэтому целесообразность выбора того или иного метода определяется непосредственно программистом Выполняемые в методе Гаусса преобразования прямого хода, приведшие матрицу А системы к треугольному виду позволяют вычислить определитель матрицы Пример   10 print "Решение системы линейных уравнений методом 20 print "Гаусса с выбором главного элемента 30 input "Задайте число уравнений"N 40 dim A(N,N),B(N),C(N,N),G(N),X(N) 50 for i=1 to N:for j=1 to N 60? "Введите A("I","J")=";:input A(i,j):next j 70? "Введите B("I")";:input B(i):next i 80 gosub 100 85 for i=1 to N 90? "X("I")=";X(I);:next I:stop 100 N1=N-1:for K=1 to N1 110 if ABS(A(K,K))>0 goto 200 120 K1=K+1:for M=K1 to N 130 if ABS(A(M,K))>0 goto 150 140 goto 165 150 for L=1 to N:V=A(K,L):A(K,L)=A(M,L) 160 A(M,L)=V:next L 165 next M 170 V=B(K):B(K)=B(M):B(M)=V 200 G(K)=B(K)/A(K,K):K1=K+1 210 for I=K1 to N:B(I)=B(i)-A(i,k)*G(k) 220 for J1=K to N J=N-J1+K C(K,J)=A(K,J)/A(K,K) 225 A(I,J)=A(I,J)-A(I,K)*C(K,J) 230 next J1:next I:next K 240 M=N:X(M)=B(M)/A(M,M) 250 M=M-1:S=0:for L=M to N1 260 S=S+C(M,L+1)*X(L+1):next L 270 X(M)=G(M)-S:If M>1 goto 250 280 return:end

12.1.4. Матричный метод Рассмотрим матричную форму записи системы: AX=B. Отсюда следует, что решение системы может быть найдено следующим образом: X=A^-1B, где A^-1 - матрица, обратная к А. Пример 02 CLS 05 PRINT "Обращение матрицы, вычисление определителя и решение" 10 PRINT "системы линейных уравнений с разными векторами B(I)" 20 INPUT "Введите порядок матрицы N="N:DIM A(N,N),B(N),S(N) 30 FOR I=1 TO N:FOR J=1 TO N:PRINT "Введите A"I","J; 40 INPUT A(I,J):NEXT J:NEXT I 50 D=1:R=1:FOR I=1 TO N:FOR J=1 TO N 80 IF A(J,I)<>0 THEN 110 90 NEXT J 100 PRINT "Матрица вырожденная":GOTO 300 110 GOSUB 190:A(I,I)=1/A(I,I):GOSUB 210 120 FOR J=1 TO N:IF J=I THEN 140 130 B=-A(J,I):A(J,I)=0:GOSUB 230 140 NEXT J:D=D/A(I,I):NEXT I:FOR I=N TO 1 STEP -1 150 IF A(I,0)=I THEN 180 160 R=-R:FOR K=1 TO N:B=A(K,I) 170 A(K,I)=A(K,A(I,0)):A(K,A(I,0))=B:NEXT K 180 NEXT I:GOTO 240 190 FOR K=1 TO N:B=A(I,K):A(I,K)=A(J,K) 200 A(J,K)=B:NEXT K:A(I,0)=J:RETURN 210 FOR K=1 TO N:IF K=I THEN 225 220 A(I,K)=A(I,I)*A(I,K):NEXT K:RETURN 225 230 FOR K=1 TO N:A(J,K)=A(J,K)+B*A(I,K):NEXT K:RETURN 240 PRINT "Элементы обращенной матрицы А^-1(I,J)" 250 FOR I=1 TO N:FOR J=1 TO N 260 PRINT "А^-1("I","J")="A(I,J):NEXT J:NEXT I 265 D=D*R:PRINT "Определитель исходной матрицы D="D 270 FOR I=1 TO N:PRINT "Введите B("I")=":INPUT B(I):NEXT I 275 FOR I=1 TO N:S(I)=0:FOR J=1 TO N 280 S(I)=S(I)+B(J)*A(I,J):NEXT J 290 PRINT "Корень X"I"="S(I):NEXT I 300 INPUT "Другой вектор B(I)? (1 - да, 0 - конец)"Q 310 IF Q=1 THEN 270 320 PRINT "Конец вычислений" 330 END

12.1.5. Метод Якоби Метод Якоби (Карл Густав Якоб Якоби (1804-1851)) представляет собой метод итераций, примененный к системе линейных уравнений вида AX=B. Перепишем эту систему уравнений в виде X=CX+D, где   В методе итераций очередное, (k+1) приближение находится из выражения

12.1.6. Метод Зейделя Метод Зейделя (Людвиг Зейдель - (1821-1896) - немецкий астроном и математик) отличается от метода итераций Якоби тем, что в нем при нахождении i-той компоненты (k+1) приближения сразу используются уже найденные компоненты (k+1) приближения с меньшими номерами:   Условием сходимости методов Якоби и Зейделя является ограничение, накладываемое на норму матрицы С: ||C||<1.

12.1.7 Метод релаксации Метод последовательной релаксации является одним из наиболее эффективных и широко используемых итерационных методов решения систем линейных алгебраических уравнений с симметричными положительно определенными матрицами А. Этот метод часто называют SOR методом (от англ. Successive Over Relaxation). Суть метода релаксации в следующем. После вычисления очередной i-той компоненты (k+1) приближения по формуле метода Зейделя Производят дополнительное смещение этой компоненты на величину, задаваемую параметром релаксации ω (0<ω<2): где волной над символом x обозначена i-тая компонента (k+1) приближения метода Зейделя. При ω=1 метод релаксации совпадает с методом Зейделя. При ω<1 его принято было называть методом последовательной верхней релаксации, а при ω>1 - методом последовательной нижней релаксации, однако с течением времени сохранилось только первое название, и его называют методом последовательной верхней релаксации для любых значений ω. Если А - симметричная положительно определенная матрица, то при любом значении параметра ω (0<ω<2): метод релаксации сходится. Выбор величины параметра обычно осуществляют экспериментальным путем с целью увеличения скорости сходимости метода Зейделя.

Рекомендации по выбору численного метода