Категорія: Методи розв’язування систем лiнiйних алгебраїчних рівнянь

Знаходження нормального псевдорозв’язку для систем з прямокутною або виродженою матрицею

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

Але це не єдине обмеження. З векторної алгебри відомо, що система лінійних рівнянь має однозначне рішення тоді і тільки тоді, коли її головний визначник не дорівнює нулю. Що ж робити, коли він (визначник) все-таки дорівнює нулю?

З класичної точки зору, системи такого типу (з прямокутною, або квадратною але виродженою матрицею) розв’язків не мають, але для них вводять поняття узагальненого розв’язку (псевдорозв’язок). Розглянемо дане поняття більш детально.

Читати далі

Знаходження розв’язку системи однорідних лінійних алгебраїчних рівнянь

Нехай задана система однорідних рівнянь наступного вигляду:

або у векторно-матричній формі , де

Якщо визначник матриці коефіцієнтів  даної системи відмінний від нуля, то в силу формул Крамера система (1) має нульовий розв’язок (), і причому єдиний.

Якщо ж , то в цьому випадку система (1) має безліч розв’язків, в тому числі і ненульові. З (2) випливає, що якщо розв’язок системи рівнянь (2) то , де – довільна стала, також є розв’язком цієї системи; якщо і – розв’язок системи (2), то сума  і  – також є розв’язком цієї системи.

Читати далі

Метод ортогоналізації. Знаходження розв’язку СЛАР методом ортогоналізації

Нахай дано систему лінійних алгебраїчних рівнянь (СЛАР) Метод ортогоналізації, яку необхідно розв’язати використовуючи метод ортогоналізації (заснований на процесі ортогоналізації системи векторів). Для цього, на першому кроці, приєднаємо вектор вільних членів Метод ортогоналізації до матриці коефіцієнтів Метод ортогоналізації. В результаті, система (1) набуде наступного вигляду:

Метод ортогоналізації

де Метод ортогоналізації – вектор-рядки (Метод ортогоналізації); Метод ортогоналізації – вектор-стовпець. Далі, систему векторів Метод ортогоналізації доповнимо додатковим вектором Метод ортогоналізації після чого, до отриманої  системи векторів Метод ортогоналізації застосуємо процес ортогоналізації, який складається з побудови ортонормованої системи Метод ортогоналізації і який реалізується за наступними рекурентними формулами:

Читати далі

Метод відображень. Розв’язок систем лінійних рівнянь методом відображень

Алгоритм методу Хаусхолдера (також відомий як метод відображень) при знаходженні розв’язку системи лінійних рівнянь Метод відображення складається з Метод відображення-го кроку (де Метод відображення – розмірність матриці), після виконання яких матриця Метод відображення системи (1) приводиться до верхньої трикутної формі. Наступним етам алгоритму є відшукання значень вектора невідомих, які отримують аналогічно, як і у методі Гаусса, тобто спочатку знаходяться значення останньої компоненти вектора невідомих, потім передостанньої і так далі.

Розглянемо даний алгоритм більш детально. Нехай в результаті виконання Метод відображення-го кроку матриця коефіцієнтів Метод відображення і вектор вільних членів Метод відображення системи (1) набули наступного вигляду:

Метод відображення

Опишемо послідовність дій Метод відображення-го крок алгоритму методу відображень. Метою даного кроку є обнулення всіх піддіагональних елементів Метод відображення-го стовпця матриці Метод відображення. Для цього визначимо вектор нормалі Метод відображення, де

Читати далі

Метод Жордана-Гаусса. Розв’язок систем лінійних рівнянь методом Жордана-Гаусса

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

Розглянемо даний метод більш детально. Для цього запишемо систему лінійних рівнянь наступного вигляду:

метод Жордана-Гаусса

Обчислювальна схема методу Жордана-Гаусса складається з Метод Жордана-Гаусса циклів, в кожному з яких послідовно за допомогою Метод Жордана-Гаусса-го рядка виключаються елементи при невідомій Метод Жордана-Гаусса в кожному рядку матриці коефіцієнтів, крім Метод Жордана-Гаусса-го. Дана схема реалізується наступним чином:

Читати далі

Розв’язок системи лінійних рівнянь використовуючи метод обертань

Метод Гаусса являється не єдиним методом який для розв’язку системи рівнянь використовує ідею зведення матриці коефіцієнтів до трикутного вигляду. Існує ще два методи, які можна віднести до категорії методів виключення невідомих, а саме метод обертань та метод відображень. Обидва ці методи базуються на представленні матриці qr_rozklad_matruci51 у вигляді добутку ортогональної матриці qr_rozklad_matruci52 та верхньої трикутної матриці qr_rozklad_matruci45. Нагадаємо, що матриця qr_rozklad_matruci52 називається ортогональною, якщо для неї виконується наступна умова: QR розклад матриці або qr_rozklad_matruci2.

Отже, перейдемо до розгляду методу обертань. Для цього, знову-таки, запишемо систему лінійних рівнянь наступного виду:

qr_rozklad_matruci3

Зазначимо, що даний метод, як і метод Гаусса, складається з прямого і оберненого ходу.

Читати далі

Метод найшвидшого спуску (градієнтний метод) для випадку системи лінійних рівнянь

Нехай потрібно знайти чисельний розв’язок системи рівнянь використовуючи метод найшвидшого спуску (градієнтний метод). Для цього, систему (1) перепишемо у наступному вигляді:

або в матрично-векторній формі , де – матриця коефіцієнтів при невідомих системи (1); – вектор-стовпець вільних члені; – вектор-стовпець невідомих.

Читати далі

Знаходження розв’язку системи лінійних рівнянь використовуючи метод оберненої матриці

Нехай маємо систему метод оберненої матриці лінійних алгебраїчних рівнянь з метод оберненої матриці невідомими Метод оберненої матриці:

Метод оберненої матриці

Для зручності систему (1) запишемо у матрично-векторній формі Метод оберненої матриці, де Метод оберненої матриці – матриця, елементами якої є коефіцієнти при невідомих системи (1), Метод оберненої матриці – вектор-стовпець вільних членів, Метод оберненої матриці – вектор-стовпець невідомих. Далі, при умові, що визначник матриці Метод оберненої матриці відмінний від нуля (Метод оберненої матриці), переходимо до обчислення елементів оберненої матриці Метод оберненої матриці.

Читати далі

Знаходження розв’язку системи лінійних рівнянь використовуючи метод квадратного кореня

Метод квадратного кореня (відноситься до категорії точних чисельних методів) використовується для знаходження розв’язку систем рівнянь, з симетричною матрицею коефіцієнтів при невідомих, тобто для систем виду:

Метод квадратного кореня

де Метод Квадратного кореня. Процес відшукання розв’язку за даним методом складається з двох етапів. Перший етап (прямий хід): виходячи з того, що Метод квадратного кореня – симетрична матриця, то її можна представити у вигляді добутку двох взаємно транспонованих між собою трикутних матриць: Метод квадратного кореня, де

Метод квадратного кореня

Перемноживши Метод квадратного кореня і Метод квадратного кореня, отримаємо деяку матрицю, яку прирівнюємо до матриці Метод квадратного кореня. В результаті отримаємо формули, для знаходження невідомих Метод квадратного кореня:

Читати далі

Метод Гаусса з вибором головного елемента

Нехай дана система лінійних алгебраїчних рівнянь виду (1), для якої потрібно знайти чисельний розв’язок:

Метод Гаусса з вибором ведучого елемента

Розглянемо розширену прямокутну матрицю, що складається з коєфіціентов системи (1) та її вільних членів:

Метод Гаусса з вибором головного елемента

Для даної матриці, згідно алгоритму методу Гаусса з вибором головного елемента, виберемо ненульовий, як правило, найбільший за модулем елемент, який не належить стовпцю вільних членів, тобто Метод Гаусса з вибором головного елемента. Нехай це буде елемент Метод Гаусса з вибором головного елемента (даний елемент також називають головним елементом). Далі, для кожного рядка матриці (2), крім рядка під номером Метод Гаусса з вибором головного елемента, обчислюємо множники:

Читати далі