Теоретичні відомості. Метод розв’язку задачі називають прямим, якщо він дозволяє отримати розв’язок після виконання кінцевого числа елементарних операцій

Метод розв’язку задачі називають прямим, якщо він дозволяє отримати розв’язок після виконання кінцевого числа елементарних операцій. До прямих методів відносяться метод Гаусса та його модифікації,

Метод Гауса. Розглянемо метод Гауса (схему єдиного поділу) розв’язку системи рівнянь. Прямий хід складається з m -1 кроків виключень.

1 Крок. виключимо невідоме з рівнянь з номерами i = 2,3,.. m. Припустимо, що . Будемо називати його провідним елементом 1-го кроку.

Знайдемо величини , i= 2,3, ...m, що звуться множниками 1-го кроку. Виключимо послідовно з другого, третього,... m -го рівнянь системи перше рівняння, помножене відповідно на . В результаті 1-го кроку отримаємо еквівалентну систему рівнянь:

Аналогічно проводяться інші кроки. Опишемо черговий k-ий крок. Припустимо, що ведучий елемент . Обчислимо множники к-го кроку: , i=k+1,...m і віднімемо послідовно з (k +1)-го, ...m -го рівнянь системи k - рівняння, помножене відповідно на . Після (m-1)-го кроку виключення отримаємо систему рівнянь

,

матриця якої є верхньою трикутною. На цьому обчислення прямого ходу закінчуються.

Зворотний хід. З останнього рівняння системи визначається . Підставляючи знайдене значення в передостаннє рівняння, отримуємо . Далі послідовно знаходимо невідомі .

LU розкладання матриці. Уявімо матрицю A у вигляді добутку нижньої трикутної матриці L і верхньої трикутної U.

Введемо в розгляд матриці

і

Можна показати, що A = LU. Це і є розкладання матриці на множники.

У методі Гаусса для обчислення масштабуючих множників потрібно ділити на провідні елементи кожного кроку. Якщо елемент дорівнює нулю (тривіальна стратегія) або близький до нуля, то можливий неконтрольований ріст похибки.

Тому часто застосовують модифікації методу Гаусса, що мають покращені обчислювальні властивості.

Схема часткового вибору. На k -му кроці прямого ходу в якості ведучого елемента вибирають максимальний по модулю коефіцієнт при невідомій в рівняннях з номерами i = k 1,..., m. Потім рівняння, відповідне обраному коефіцієнту з номером , міняють місцями з к -им рівнянням системи для того, щоб головний елемент зайняв місце коефіцієнта . Після цієї перестановки виняток проводять як в схемі єдиного ділення. У цьому випадку всі масштабуючі множники по модулю менше одиниці і схема володіє обчислювальною стійкістю.

Норми векторів і матриць. Позначимо через – точний розв’язок системи, а через – наближений розв’язок системи.

Нормою вектора називається число , що задовольняє трьом аксіомам:

1) , причому тоді і тільки тоді, коли ;

2) для довільного вектора та довільного числа ;

3) для довільних векторів та .

Приведемо приклад норм, що найчастіше використовуються:

Відносна похибка вектора вводиться за допомогою формули:

Нормою матриці А називається величина . Введена норма має наступні властивості, аналогічні властивостям норми вектора:

1) , причому тоді і тільки тоді, коли ;

2) для довільної матриці та довільного числа ;

3) для довільних матриць та .

4)

Кожній із векторних норм відповідає своя підлегла норма матриці:

В оцінках замість норми використовується евклідова норма матриці

Відносна похибка матриці вводиться аналогічно до похибки вектора за допомогою формули: .

Оцінювати теоретично похибку розв’язку системи за похибками вхідних даних можна за формулою

,

де x* - розв’язок системи A*x*=b*

Число обумовленості квадратної матриці A визначається, як

cond(A) = ||A||·||A^-1||

Число обумовленості має наступне значення: якщо машинна точність, з якою здійснюються всі операції з дійсними числами, дорівнює ε, то після розв’язку системи лінійних рівнянь Ax = b, результат буде отримано з відносною похибкою порядку ε·k(A). Хоча число обумовленості матриці залежить від вибору норми, якщо матриця добре обумовлена, то її число обумовленості буде малим при будь-якому виборі норми а якщо вона погано обумовлена, то її число обумовленості буде великим при будь-якому виборі норми.

Якщо cond(A)=1-10, матриця вважається добре обумовленою, а коли cond(A) >>10²-10³ - погано обумовленою.