Skip to main content
LibreTexts - Ukrayinska

5.3: Поворотний

  1. Last updated
  2. Save as PDF
  • Page ID
    79624

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    У нашому описі алгоритму гаусової елімінації до цих пір ви, можливо, помітили проблему. Під час процесу скорочення рядків ми повинні помножити рядки на коефіцієнт\(A'_{mn}/A'_{nn}\) (де\(\mathbf{A}'\) позначає поточну матрицю). Якщо\(A'_{nn}\) трапляється нуль, коефіцієнт виривається, і алгоритм виходить з ладу.

    Щоб обійти цю складність, додаємо додатковий крок до процедури зменшення рядів. Коли ми крокуємо вперед через номери рядків\(n = 0, 1, \cdots, N-1\), ми робимо наступне для кожного\(n\):

    • Поворотні: пошук елементів матриці на і нижче діагонального елемента в\((n,n)\), і знайти рядок\(n'\) з найбільшим значенням\(|A'_{n'n}|\). Потім поміняти місцями ряд\(n\) і ряд\(n'\).
    • Продовжуйте з іншим алгоритмом, усунувши\(A'_{mn}\) елементи нижче діагоналі.

    Ви повинні бути в змозі переконати себе, що (i) поворот не змінює рішення, і (ii) це не змінює масштабування часу виконання фази скорочення рядків, яка залишається\(O(N^3)\).

    Окрім запобігання надмірному виходу алгоритму з ладу, поворот покращує його числову стабільність. Якщо\(A'_{nn}\) ненульовий, але дуже малий за величиною, поділ на нього дасть дуже великий результат, що призводить до втрати числової точності з плаваючою комою. Отже, вигідно міняти місцями ряди навколо, щоб гарантувати, що\(A'_{nn}\) величина була якомога більшою.

    При спробі повороту може статися, що всі значення діагоналі та нижче діагоналі дорівнюють нулю (або досить близькі до нуля в межах нашого допуску з плаваючою\(|A'_{n'n}|\) комою). Якщо це станеться, то це вказує на те, що наша вихідна\(\mathbf{A}\) матриця є одниною, тобто вона не має зворотного. Отже, процедура повороту має додаткову перевагу, допомагаючи нам вловити випадки, коли немає дійсного рішення системи рівнянь; у таких випадках алгоритм гаусової елімінації повинен перервати.

    5.3.1 Приклад

    Давайте попрацюємо на прикладі гаусової елімінації з поворотом, використовуючи задачу в попередньому розділі:

    \[\left[\begin{array}{ccc|cc} 1 & 2 & 3 & 3 & 6 \\ 3 & 2 & 2 & 4 & 8 \\ 2 & 6 & 2 & 4 & 2 \end{array}\right].\]

    Фаза скорочення рядів йде наступним чином:

    • (\(n=0\)): Pivot, міняючи рядки\(0\) та рядки\(1\):
      \[\left[\begin{array}{ccc|cc} 3 & 2 & 2 & 4 & 8 \\ 1 & 2 & 3 & 3 & 6 \\ 2 & 6 & 2 & 4 & 2 \end{array}\right].\]
    • (\(n=0\)): Усунути елемент за адресою\((1,0)\):
      \[\left[\begin{array}{ccc|cc} 3 & 2 & 2 & 4 & 8 \\ 0 & 4/3 & 7/3 & 5/3 & 10/3 \\ 2 & 6 & 2 & 4 & 2 \end{array}\right].\]
    • (\(n=0\)): Усунути елемент за адресою\((2,0)\):
      \[\left[\begin{array}{ccc|cc} 3 & 2 & 2 & 4 & 8 \\ 0 & 4/3 & 7/3 & 5/3 & 10/3 \\ 0 & 14/3 & 2/3 & 4/3 & -10/3 \end{array}\right].\]
    • (\(n=1\)): Pivot, міняючи рядки\(1\) та рядки\(2\):
      \[\left[\begin{array}{ccc|cc} 3 & 2 & 2 & 4 & 8 \\ 0 & 14/3 & 2/3 & 4/3 & -10/3 \\0 & 4/3 & 7/3 & 5/3 & 10/3 \end{array}\right].\]
    • (\(n=1\)): Усунути елемент за адресою\((2,1)\):
      \[\left[\begin{array}{ccc|cc} 3 & 2 & 2 & 4 & 8 \\ 0 & 14/3 & 2/3 & 4/3 & -10/3 \\0 & 0 & 15/7 & 9/7 & 30/7 \end{array}\right].\]

    Потім фаза зворотного заміщення триває як зазвичай. Ви можете перевірити, чи дає він ті самі результати, які ми отримували раніше.