Численные методы.

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by ~Lexx~, 8 Nov 2007.

  1. ~Lexx~

    ~Lexx~ Elder - Старейшина

    Joined:
    30 Sep 2006
    Messages:
    195
    Likes Received:
    28
    Reputations:
    0
    Иногда приходиться решать СЛАУ или что-нить еще, то что требует нахождения численного решения. Здесь в этой ветке постоянно висят подобные задачи. Большинство решений - безграмотны, если не сказать больше. В общем опишу как следует добиваться наименьших машинных затрат, как грамотнее организовать алгоритм. В общем разберу это все на примере Систем Линейных Алгебраических Уравнений (Слау).

    Итак существует две большие группы алгоритмов - Прямые методы - это когда
    за вполне определенное число шагов мы находим точное решение(если не учитывать ошибки вычисления и округления) и Итерационные методы, когда мы строим последовательность приближений. Ну впринцие есть еще класс смешанных методов, но об этом позже. Конечно прямые методы позволяют найти точное решение(ну не совсем) , но не всегда мы можем найти это решение. К тому же прямые методы требуют много ресурсов - может нехватить. В общем хватит демагогии.

    Прямые методы

    Метод Гаусса

    Пусть у нас задана СЛАУ в виде A*x = b, где А - матрица заполненная коэффициентами х - неизвестный столбец решений, а b - столбец решений(правая часть каждого уравнения).
    В чистом виде метод Гаусса приводит матрицу А к верхне-треугольному виду - Элементы основной диагонали равны 1 а элементы под ней - равны 0.

    Весь метод состоит из 2-х частей ПРЯМОЙ ХОД

    Приводим матрицу к нужному виду:

    |XXXX| |X1| |b1|=>|1XXX| |X1| |q1|
    |XXXX| |X2| |b2|=>|01XX| |X2| |q2|
    |XXXX|*|X3|=|b3|=>|001X|* |X3|= |q3|
    |XXXX| |X4| |b4|=>|0001| |X4| |q4|

    В такой послдовательности [​IMG]
    Таким образом мы автоматически получаем решение последнего уравнения (последний х) и начинаем вычислять все уравнения снизу вверх. это обратный ход.

    все это замечательно - да вот только количество действий только на прямом ходу х^3/3. К тому же в современных выч машинах есть ошибка округления - реально считаеться возмущенная система уравнений.
    [A+F(1)]x=b-h(1), где F(1) и h(1). Не стану приводить здесь математические рассчеты - скажу, что метод неустойчив - могут получиться огромные погрешности. Это возникает из-за того, что в ходе перевножения/деления могут появиться очень большие элементы, и очень маленькие - это плохо влияет на двоичное округление.
    Решаеться это просто-мы выбираем строку которую вычитаем из остальных так, чтобы ее первый елемент(тот который вконце прямого ходя станет 1 ) был максимальным - Для этого последовательно меняем строки местами(не зыбаваем каждый раз при сдвиге менять знак матрицы). в общем при этом получаем коэффициент роста элементов матрицы не превышает 2^(n-1). Это многовато - метод условно устойчивый(тоесь что он выкинет - нельзя точносказать). Чтобы окончательно добить эту радость главный элемент выбирают по всей матрице - той что под отработавшей строкой. Здесь меняют местами не только строки, но и столбцы. Здесь коэффициент роста пропорционален n.

    Итог: Метод подходит для грубых оценок не очень больших матриц. Ну скажем 1500 на 1500 не целочисленных элементов.

    Метод LU факторизации.

    Этот метод также называют компактным методом гауса.
    Итак вместо того чтобы решать систему Ax=b, мы представим A = LU где L-нижняя треугольная матрица, а U- верхняя. Причем одна из диагоналей - единичная.Если единичная диагональ у L - это метод Дуллитла, а если U - метод краута. Рассмотрим метод краута. Тогда приходим к уравнению вида
    LUx=b
    Это решаеться в два шага.
    1)Ly=b
    2)Ux=y
    здесь снова опущу математические вычисление - они не суть как важны - главное результат - получаем количество операций - N^2(Это кол-во операций по вычислению решения, используя готовые матрицы L и U).

    XXXXX X0000 XXXXX
    XXXXX XX000 0XXXX
    XXXXX=XXX00*00XXX
    XXXXX XXXX0 000XX
    XXXXX XXXXX 0000X


    Из схемы видно, что можно выразить элементы матриц L и U.(провести LU факторизацию). Здесь также опущу вычисления.Итого факторизация занимает n^3\3 операций. Этот метод выгодно использовать, если нужно посчитать
    несколько раз одну и ту же систему, используя различнае ответы тк основные вычисления - это факторизация.

    Метод LU-факторизации, если не делать никаких специальных усилий, характеризуется такими же оценками нормы матрицы возмущения и относительной ошибки, как и метод Гаусса. Но здесь есть одна важная фича-Здесь улучшению точности помогает операция скалярного накопления. Sum(x(n)*y(n)). Во многих ЭВМ эта функция реализованна на аппаратном уровне.

    Метод Холесского

    Исключительно эффективную реализацию метода LU-факторизации можно получить, если ограничиться классом линейных систем с симметрической положительно определенной матрицей A. тогда матрицу А можно представить в виде A = L*Lтрансп. L - Нижняя треугольная матрица.Эффективность этого метода мы получаем при разложении(тк надо раскладывать только 1 матрицу) ну и соответственно получаем что нужно выполнить n^3/6 операций при факторизации и n извлечений квадратного корня.Что бы избежать операции извлечния корня, сделаем другую замену.
    L=L'diag{i(jj)} Где L' - матрица вычисленная раньше по схеме холесского. В общем здесь у нас появляються такие результаты. Количество умножений при такой организации алгоритма составляет приблизительно и не содержит операции извлечения квадратного корня.

    Можно показать, что в схеме Холесского коэффициент роста элементов матрицы A равен 1.Таким образом, чтобы ошибки округления при реализации схемы Холесского были малыми, не требуется никаких перестановок строк либо столбцов. Наименьшая погрешность численного решения достигается при привлечении операции скалярного накопления.

    Для начала хватит. Дальше опишу итерационные методы. В общем это и так длинновато и нудновато получилось. Простите, если не угодил кому-то. Если нужны точные вычисления - легко приложу. Это был только пример. Здесь я его выложил, чтобы начинающие писатели/программеры поняли - невозможно создать абсолютно точно работающую программу. И если у вс есть хотя бы один не целочисленный параметр - вы должны задумываться о оптимизаци. Эир нужно делать повсеместно - при интерполяции функции, при построении графиков,и при банальных расчетах.
     
    #1 ~Lexx~, 8 Nov 2007
    Last edited by a moderator: 9 Nov 2007
    3 people like this.
  2. Ky3bMu4

    Ky3bMu4 Elder - Старейшина

    Joined:
    3 Feb 2007
    Messages:
    487
    Likes Received:
    284
    Reputations:
    42
    Метод Гаусса возможен и без обратного хода, т.е.:

    Code:
    х х х  
    x x x
    x x x   
      ||
    1 x x
    0 x x
    0 x x
       ||
    1 0 x
    0 1 x
    0 0 x
       ||
    1 0 0
    0 1 0
    0 0 1
    
    P.S.
    Фамилии математиков с большой буквы напиши. ;)
     
    #2 Ky3bMu4, 9 Nov 2007
    Last edited: 9 Nov 2007
  3. ~Lexx~

    ~Lexx~ Elder - Старейшина

    Joined:
    30 Sep 2006
    Messages:
    195
    Likes Received:
    28
    Reputations:
    0
    Конечно это так, но не забывай - основная работа в методе Гаусса - это как раз прямой ход. А теперь ты увеличиваешь его, тк раньше каждая последующая активная матрица уменьшалась - теперь же остаеться такой, же. При больших размерах матрицы - это очень значительно.
     
  4. da_ff

    da_ff Elder - Старейшина

    Joined:
    11 Jul 2006
    Messages:
    118
    Likes Received:
    22
    Reputations:
    26
    вот!!! действительно, полезный пост. я так понимаю, должно быть продолжение?
     
  5. ~Lexx~

    ~Lexx~ Elder - Старейшина

    Joined:
    30 Sep 2006
    Messages:
    195
    Likes Received:
    28
    Reputations:
    0
    В разработке. Пишите - что вам надо - по возможности отпишусь. Сейчас пишу о итерационных методах. Там немножко побольше
     
  6. return

    return New Member

    Joined:
    23 Oct 2010
    Messages:
    125
    Likes Received:
    3
    Reputations:
    1
    не знаю относится сюда или нет, но кто может выложить метод Шимбела. Дискретку учил уже давненько, а метод в и-нет смотрю редкий. Помню что там в матрице перемножаются коэффициенты, а потом сравниваются и если меньше то меняются, и так до тех пор пока не достигнет придела что уже нечего менять. А если кто выложит ещё и в .cpp то вообще будет здорово!
     
Loading...