Метод Прогонки

Тема в разделе "Pascal and Delphi", создана пользователем SLava-markov, 19 дек 2011.

Статус темы:
Закрыта.
  1. SLava-markov

    SLava-markov Гость

    Нужно составить алгоритм и написать программу. Через два дня надо сдать, а у меня ни того, ни второго. Теория:
    Метод прогонки.

    Он является модификацией метода Гаусса для частного случая разреженных систем — системы уравнений с трехдиагональной матрицей. Такие системы получаются при моделировании некоторых инженерных задач, а также при численном решении краевых задач для дифференциальных уравнений.
    Запишем систему уравнений в виде:
    b1x1+c1x2 =d1,
    a2x¬1+b2x2+c2x3 =d2,
    a3x2+b3x3+c3x4 =d3,
    …………………………………………………………… (1),
    an-1xn-2+bn-1xn-1+cn-1xn=dn-1,
    anxn-1+bnxn=dn.
    На главной диагонали матрицы этой системы стоят элементы b1,b2…,bn, над ней – элементы c1,c2,...,cn-1, под ней – элементы a2,a3,…,an. При этом обычно все коэффициенты bi не равны нулю.
    Метод прогонки состоит из двух этапов — прямой прогонки (аналога прямого хода метода Гаусса) и обрат¬ной прогонки (аналога обратного хода метода Гаусса). Прямая прогонка состоит в том, что каждое неизвестное xi выражается через xi+1 c помощью прогоночных коэф¬фициентов Ai, Bi:
    xi=Aixi+1+Bi, i=1,2,…,n-1. (2).
    Из первого уравнения системы (1) найдем
    x1= - c_1/b_1 x2 + d_1/b_1 .
    С другой стороны, по формуле (2) x1=A1x2+B1 . При¬равнивая коэффициенты в обоих выражениях для x1, по¬лучаем
    A1= - c_1/b_1 , B1= d_1/b_1 (3).
    Из второго уравнения системы (1) выразим x2 через x3 заменяя x1 по формуле (2):
    a2(A1x2+B1)+b2x¬2+c2x3=d2.
    Отсюда найдем
    x2= (-c_(2X_3 )+d_2-a_2 B_1)/(a_2 A_1+b_2 ),
    или
    x2=A2x3+B2,
    A2= - c_2/e_2 , B2= (d_(2-) a_2 B_1)/e_2 , e2=a2A1+b2.
    Аналогично можно вычислить прогоночные коэффициен¬ты для любого номера i:
    Ai= - c_i/e_i , Bi= (d_i-a_i B_(i-1))/e_i , (4).
    ei=aiAi-1+bi, i=2,3,…,n-1.
    Обратная прогонка состоит в последовательном вы¬числении неизвестных хi. Сначала нужно найти хп. Для этого воспользуемся выражением (2) при i= n — 1 и последним уравнением системы (1). Запишем их:
    xn-1=An-1xn+Bn-1,
    anxn-1+bnxn=dn.
    Отсюда, исключая xn-1 находим
    xn= (d_n-a_n B_(n-1))/(b_n+a_n A_(n-1) ).
    Далее, используя формулы (2) и выражения для прогоночных коэффициентов (3), (4), последова¬тельно вычисляем все неиз¬вестные xn-1, xn-2,…,x1.

    При анализе алгоритма метода прогонки надо учи¬тывать возможность деления на нуль в формулах (4), Можно показать, что при выполнении условия преоб¬ладания диагональных эле¬ментов, т. е. если |bi|≥ |ai|+|ci|, причем хотя бы для одного значения i имеет место строгое неравенство, деления на нуль не возника¬ет, и система (1) имеет единственное решение.

    Приведенное условие пре¬обладания диагональных эле¬ментов обеспечивает также устойчивость метода прогон¬ки относительно погрешно¬стей округлений. Последнее обстоятельство позволяет использовать метод прогон¬ки для решения больших систем уравнений. Заметим, что данное условие устойчи¬вости прогонки является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем вида (1) метод прогонки оказывается устойчивым даже при нарушении условия преобладания диагональных элементов.








    Пример.
    2.05x1+1.07x2 =1.78
    1.83x1+2.42x2-1.02x3 =2.45
    -3.49x2+1.51x3=3.26
    Решение:
    Вычисляем прогоночные коэффициенты:
    A1= - c_1/b_1 = - 1.07/2.05 = - 0.522
    B1= d_1/b_1 = 1.78/2.05 = 0.868
    ei=aiAi-1+bi, i=2,3,…,n-1
    ei= - 0.522*1.83+2.42=1.465
    A2= - c_2/e_2 = (-1.02)/1.465 = 0.696
    B2= (d_(2-) a_2 B_1)/e_2 = (2.45-1.83*0.868)/1.465 = 0.588
    Вычисляем неизвестные xi:
    xn= (d_n-a_n B_(n-1))/(b_n+a_n A_(n-1) ) = (3.26-3.49*0.588)/(1.51-3.49*0.696) = -5.78
    xi=Aixi+1+Bi, i=1,2,…,n-1.
    x2= 0.696*(-5.78)+0.588 = - 3.435
    x1= - 0.522*(-3.435)+0.686 = 2.611
    Получили решение системы:
    X=[(2.661
    -3.435
    -5.78)].
     
  2. nayke

    nayke Well-Known Member

    Регистрация:
    4 авг 2010
    Сообщения:
    310
    Симпатии:
    0
    И читаете вы наверное плохо. Денег сколько?
     
  3. Corp

    Corp Гость

    есть готовый метод прогонки, написанный на Си
    ------------------------------
    ICQ 451099546 пиши, о цене договоримся
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей