Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Метод Гауса для розв’язування систем лінійних алгебраїчних рівнянь
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2011
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Комп’ютерні методи дослідження інформаційних процесів та систем
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ,МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ІКТА
кафедра БІТ
З В І Т
до лабораторної роботи №2
з курсу: «Комп'ютерні методи дослідження інформаційних процесів і систем»
на тему: «Метод Гауса для розв’язування систем лінійних
алгебраїчних рівнянь»
Мета роботи – ознайомлення з прямими методами розв’язування систем лінійних алгебраїчних рівнянь.
1. Методи розв’язування систем лінійних алгебраїчних рівнянь
Нехай задано систему лінійних алгебраїчних рівнянь:
,
де А – квадратна невироджена матриця розмірності , X – вектор-стовпець невідомих розмірності n, В – вектор-стовпець вільних членів розмірності n.
Методи розв’язування систем такого виду поділяються на дві групи : прямі та ітераційні.
1) Прямі методи зводяться до скінчених алгоритмів для обчислення коренів рівнянь (тобто розв’язки шукають за певними формулами). Вони дають розв’язки після виконання відомого для даного n (n – порядок системи) числа арифметичних операцій.
Іншими словами, прямими методом розв’язування лінійної системи називають будь-який метод, котрий дозволяє знайти елементи вектора X з допомогою скінченого числа елементарних математичних операцій: додавання, віднімання, ділення, множення, та, можливо, кореня квадратного.
Оцінити ефективність будь-якого методу можна за допомогою таких основних характеристик:
числа операцій, необхідних для реалізації даного методу;
об’єму пам’яті;
чутливості до переносу похибок заокруглення (або обчислювальної стійкості).
Практично всі прямі методи розв’язування систем базуються на зведені матриці А до матриці простішої структури – діагональної (тоді розв’язок очевидний) або трикутної, та методів розв’язування таких систем.
До групи прямих методів розв’язування систем лінійних алгебраїчних рівнянь належать:
– метод Гаусса
а) класичний метод Гаусса із зведенням матриці А до верхньої трикутної матриці і одержанням розв’язків з допомогою обернених підстановок. Число операцій (вартість методу) – операцій додавання, множення та операцій ділення (можна ними знехтувати в порівнянні з ).
Прямі методи розв’язування систем лінійних алгебраїчних рівнянь
Класичний метод Гаусса.
Розглянемо систему рівнянь четвертого порядку:
(1)
Зауважимо, що елементи вектора-стовпчика вільних членів занесені в матрицю коефіцієнтів А.
Будемо вважати, що . З першого рівняння знаходимо х1:
, (2)
де , .
З допомогою рівняння (2) можна виключити з решти рівнянь, для чого достатньо підставити праву частину (2) замість в друге, третє і четверте рівняння системи. Це і є першим кроком – кроком виключення невідомого .
Перехід від початкової системи (1) до новоствореної:
відбувається за такою формулою:
Другий крок – виключення невідомого відбувається аналогічно:
Третій крок – виключення невідомого
,
;
Останнє рівняння модифікованої системи можна переписати у вигляді:
де
або .
Отже, в результаті прямого ходу одержимо систему рівнянь:
Знаходження невідомих проводиться в оберненому ході методу Гаусса шляхом зворотніх підстановок.
Якщо п – кількість рівнянь (порядок) системи, то програмування обчислювального процесу проводиться так:
L – кількість кроків виключення ;
j – позначення другого індексу при визначенні коефіцієнта ;
і – номер рядка системи ;
k – номер стовпця.
Можна записати, що для всіх
Обернений хід: ; , .
Отже, обчислювальна схема прямого ходу методу Гаусса має вигляд:
Для
Для
Для
Для
i піддається спрощенню.
Початкове обчислення всіх коефіцієнтів c не є обов’язковим. Це випливає з наступного. Наприклад, перехід від початкової системи коефіцієнтів до наступної відбувається так:
Наприклад, коефіцієнти першого чи другого стовпця нової системи утворюються за правилом
,
або
Отже, визначивши, наприклад c12 зразу ж можна переходити до визначення коефіцієнтів нової системи і т.п. Таким чином цикли по J i по K можна об’єднати (оскільки J i K змінюються в однакових межах).
Якщо замінити на (адже верхній рядок коефіцієнтів матриці А на наступному кроці виключення не перераховується, а тому може бути перерахований і використаний як коефіцієнти ) та цикли по J та по K об’єднати в один, одержимо загальну форму методу виключення Гаусса із стовпцевою формою розкладу матриці А до трикутного вигляду:
В кінці цих перетворень (зворотній хід методу) одержимо:
Таким чином, стовпцева форма розкладу зображується наступною обчислювальною схемою:
Для до
Для до +1
(3)
В цій обчислювальній схемі права частина системи (1) також обробляється в ході зведення матриці А до трикутного вигляду. Тобто коефіцієнти приєднані до і-го рядка матриці А (член ) (саме тому в циклі по "k" верхня межа зростає до ). Можна залишити на місці, не вносячи в масив А. В цьому випадку в результаті виконання прямого ходу методу Гаусса одержується система рівнянь:
(4)
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
.
Обернений хід при стовпчиковій формі розкладу описується загальною формулою:
, (5)
Розглянемо тепер рядкову форму розкладу матриці А. Вона базується на зведенні системи лінійних рівнянь до трикутного вигляду. Для цього спочатку нормують перше рівняння системи (1), ділячи його на а11(0), тобто роблять коефіцієнт при х1 рівним 1. Потім це перше рівняння домножують відповідно на коефіцієнт аі,1(0) при х1 всіх інших рівнянь і послідовно віднімають від усієї решти рівнянь. В результаті х1 буде виключене із всіх рівнянь, крім першого. На другому кроці виключають х2 з третього, четвертого, ..., п –го рівнянь. Цю процедуру повторюють до тих пір, доки вся система не буде зведена до такого трикутного вигляду:
(6)
Рядкова форма зображається наступною обчислювальною схемою (у випадку внесення коефіцієнтів b в матрицю A):
Для до
Для до
(7)
Для до +1
Тобто, на відміну від стовпчикової форми, обчислення коефіцієнтів нової матриці відбувається по рядках. Результат же одержується той самий.
При (обертанні) обчисленні оберненої матриці доцільно використовувати розклад матриці А до трикутного вигляду за рядковою формою.
2. Завдання до лабораторної роботи
Розв’язати систему лінійних алгебраїчних рівнянь методом Гаусса -класичний.
S=0,2*k k=4
b=0,2*p p=5
3. Блок-схема алгоритму програми
4. Список ідентифікаторів констант, змінних, функцій,
використаних у блок-схемі алгоритму і програмі,
та їх пояснення
Void main( ) – головна функція програми
i, k,l,j – змінні , які використовуюся в циклі
cout<< - який забезпечує введення в програму вхідних величин
cin>> - метод класу , який забезпечує зчитування значення з клавіатури
n, m – змінні, які визначають розмірність матриці
a[n][m] - Змінна масив котра зберігає матрицю, і проміжні результати обчислень
x[n] - змінна масив (одновимірний), який зберігає значення коренів рівняння
5. Текст програми
#include "stdafx.h"
#include<stdio.h>
#include<math.h>
#include <iostream>
using namespace Tarasko ;
void main(void)
{
int i,k,l,j;
double a[4][5],x[4];
int n=4;
int m=5;
for(i=0;i<n;i++)
{
for(k=0;k<m;k++)
{
cout<<" a["<<i+1<<"."<<k+1<< "]= ";
cin>>a[i][k];
}
cout<<"\n";
}
for(l=0;l<(n-1);l++){
for(j=l+1;j<(n+1);j++){
a[l][j]=-a[l][j]/a[l][l];
for(i=l+1;i<n;i++){
a[i][j]+=a[i][l]*a[l][j];}}};
x[n-1]=-(a[n-1][n]/a[n-1][n-1]);
for(i=n-2;i>=0;i--)
{
x[i]=a[i][n];
for(k=i+1;k<n;k++)
{ x[i]+=a[i][k]*x[k];}
}
for(i=0;i<n;i++)
cout<<"\n""x["<<i+1<<"]="<<x[i];
cin>>a[i][k];
}
6. Результат виконання програми
a[1.1]= 8.3
a[1.2]= 3.42
a[1.3]= 4.1
a[1.4]= 1.9
a[1.5]= -9.55
a[2.1]= 3.92
a[2.2]= 8.45
a[2.3]= 6.98
a[2.4]= 2.46
a[2.5]= 12.21
a[3.1]= 3.77
a[3.2]= 8.01
a[3.3]= 8.04
a[3.4]= 2.28
a[3.5]= 14.45
a[4.1]= 2.21
a[4.2]= 2.85
a[4.3]=1.69
a[4.4]= 6.99
a[4.5]= -8.35
x[1]= 2.35204
x[2]= -1.26346
x[3]=-2.05635
x[4]= 1.4632
Висновок: на цій лабораторній роботі я ознайомися з прямими методами розв’язування систем лінійних алгебраїчних рівнянь. В даній програмі я використовував метод Гауса(класичний)
17.03.2013 13:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора