ЗМІСТ
Введення
1 Постановка завдання
2 Математичні та алгоритмічні основи рішення задачі
2.1 Схема єдиного ділення
2.1.1 Прямий хід
2.1.2 Зворотний хід
2.2 Метод Гаусса з вибором головного елемента по стовпцю
3 Функціональні моделі та блок-схеми виконання завдання
4 Програмна реалізація рішення задачі
5 Приклад виконання програми
Висновок
Список використаних джерел та літератури
ВСТУП
Рішення систем лінійних алгебраїчних рівнянь - одна з основних задач обчислювальної лінійної алгебри. Хоча завдання вирішення системи лінійних рівнянь порівняно рідко представляє самостійний інтерес для додатків, від уміння ефективно вирішувати такі системи часто залежить сама можливість математичного моделювання найрізноманітніших процесів з застосуванням ЕОМ. Значна частина чисельних методів розв'язання яких (особливо - нелінійних) завдань включає в себе вирішення систем лінійних рівнянь як елементарний крок відповідного алгоритму.
Одна з труднощів практичного вирішення систем великої розмірності пов'язана з обмеженістю оперативної пам'яті ЕОМ. Хоча обсяг оперативної пам'яті новостворюваних обчислювальних машин зростає дуже швидко, тим не менш, ще швидше зростають потреби практики у вирішенні завдань все більшої розмірності. У значній мірі обмеження на розмірність розв'язуваних систем можна зняти, якщо використовувати для зберігання матриці зовнішні запам'ятовуючі пристрої. Однак у цьому випадку багаторазово зростають як витрати машинного часу, так і складність відповідних алгоритмів. Тому при створенні обчислювальних алгоритмів лінійної алгебри велику увагу приділяють способам компактного розміщення елементів матриць в пам'яті ЕОМ.
На щастя, додатки дуже часто призводять до матриць, в яких число ненульових елементів багато менше загального числа елементів матриці. Такі матриці прийнято називати розрідженими. Одним з основних джерел розріджених матриць є математичні моделі технічних пристроїв, що складаються з великого числа елементів, зв'язки між якими локальні. Найпростіші приклади таких пристроїв - складні будівельні конструкції і великі електричні кола.
Відомі приклади вирішених в останні роки завдань, де число невідомих сягало сотень тисяч. Природно, це було б неможливо, якби відповідні матриці не були розрідженими (матриця системи з 100 тис. рівнянь у форматі подвійної точності зайняла б близько 75 Гбайт).
Одним з найпоширеніших методів розв'язування систем лінійних рівнянь є метод Гауса. Цей метод (який також називають методом послідовного виключення невідомих) відомий у різних варіантах вже більше 2000 років.
Обчислення за допомогою методу Гаусса полягають у послідовному вилученні невідомих із системи для перетворення її до еквівалентної системі з верхньою трикутною матрицею. Обчислення значень невідомих виробляють на етапі зворотного ходу.
Метою даної курсової роботи є чисельне рішення системи лінійних рівнянь за допомогою методу виключення Гауса з вибором головного елемента по стовпцю.
1 Постановка завдання
Завдання ставиться наступним чином. Нехай потрібно знайти рішення системи лінійних алгебраїчних рівнянь
a 1,1 x 1 + a 1,2 x 2 + a 1,3 x 3 +. . . + A 1, n x n = b 1
a 2,1 x 1 + a 2,2 x 2 + a 2,3 x 3 +. . . + A 2, n x n b = 2
(1)
a n, 1 x 1 + a n, 2 x 2 + a n, 3 x 3 +. . . + A n, n xn = b n
або у векторній формі
AX = B
де A-матриця коефіцієнтів; X - вектор невідомих; B-вектор правих частин.
Будемо вважати, що = det A 0 тобто рішення існує і єдино.
Розглянемо спочатку прямі методи. У явному вигляді рішення системи (1) записується у вигляді формул Крамера
x i = i /
де i - визначник матриці, яка виходить з матриці A шляхом заміни i-того стовпця на стовпець правих частин.
Цей метод дуже неекономічний тому що для його застосування потрібно (n +1)! операцій, тому на практиці використовуються різні варіанти методу виключення змінних (Гауса). Метод виключення змінних складається з двох етапів: прямого ходу, що полягає в перетворенні вихідної системи до системи з трикутною матрицею коефіцієнтів, і зворотного ходу, тобто рішення системи з трикутною матрицею.
Приклад 1. Р ешіть наступну систему за допомогою методу виключення Гауса з вибором головного елемента по стовпцю:
.
Рішення:
.
Приклад 2. Р ешіть наступну систему за допомогою методу виключення Гауса з вибором головного елемента по стовпцю:
.
Складемо розширену матрицю системи.
.
Рішенням системи є: x = 1, y = 2, z = 3.
2 Математичні та алгоритмічні основи рішення задачі
2.1 Схема єдиного ділення
Розглянемо спочатку найпростіший варіант методу Гауса, званий схемою єдиного ділення.
2.1.1 Прямий хід
Прямий хід складається з n - 1 кроків винятку.
1-й крок. Метою цього кроку є виняток невідомого x1 з рівнянь з номерами i = 2, 3, ..., n. Припустимо, що коефіцієнт a11 = 0. Будемо називати його головним елементом 1-го кроку.
Знайдемо величини
qi1 = ai1/a11 (i = 2, 3, ..., n),
звані множниками 1-го кроку. Віднімемо послідовно з другого, третього, n-го рівнянь системи перше рівняння, помножене відповідно на q21, q31, qn1. Це дозволить перетворити на нуль коефіцієнти при x1 у всіх рівняннях, крім першого. У результаті отримаємо еквівалентну систему
a 11 x 1 + a 12 x 2 + a 13 x 3 + ... + a 1 nxn = b 1,
a22 (1) x2 + a23 (1) x3 + ... + a2n (1) xn = b2 (1),
a32 (1) x2 + a33 (1) x3 + ... + a3n (1) xn = b3 (1),
an2 (1) x2 + an3 (1) x3 + ... + ann (1) xn = bn (1).
в якій aij (1) і bij (1) обчислюються за формулами
aij (1) = aij - qi1a1j bi (1) = bi - qi1b1.
2-й крок. Метою цього кроку є виняток невідомого x2 з рівнянь з номерами i = 3, 4, ..., n. Нехай a22 (1) ≠ 0, де a22 (1) - коефіцієнт, званий головним (або ведучим) елементом 2-го кроку. Обчислимо множники 2-го кроку
qi2 = ai2 (1) / a22 (1) (i = 3, 4, ..., n)
і віднімемо послідовно з третього, четвертого, ..., n-го рівняння системи друге рівняння, помножене відповідно на q32, q42, ..., qm2.
У результаті отримаємо систему
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 1 nxn = b 1,
a22 (1) x2 + a23 (1) x3 + a2n (1) = b2 (1),
a33 (2) x3 + a3n (2) xn = b3 (2),
an3 (2) x3 + ann (2) xn = bn (2)
Тут коефіцієнти aij (2) і bij (2) обчислюються за формулами
aij (2) = aij (1) - qi2a2j (1), bi (2) = bi (1) - qi2b2 (1).
Аналогічно проводяться інші кроки. Опишемо черговий k-й крок.
k-й крок. У припущенні, що головний (провідний) елемент k-го кроку akk (k-1) відмінний від нуля, обчислимо множники k-го кроку
qik = aik (k-1) / akk (k-1) (i = k + 1, ..., n)
і віднімемо послідовно з (k + 1)-го, ..., n-го рівнянь отриманої на попередньому кроці системи ke рівняння, помножене відповідно на
qk +1, k, qk +2, k, ..., qnk.
Після (n - 1)-го кроку виключення отримаємо систему рівнянь
a11x1 + a12x2 + a13x3 + a1nxn = b1
a22 (1) x2 a23 (1) x3 + ... + a2n (1) xn = b2 (1)
a33 (2) x3 + a3n (2) xn = b3 (2),
ann (n -1) xn = bn (n -1)
Матриця A (n-1) якої є верхньою трикутною. На цьому обчислення прямого ходу закінчуються.
2.1.2 Зворотний хід
Зворотний хід. З останнього рівняння системи знаходимо xn. Підставляючи знайдене значення xn в передостаннє рівняння, отримаємо xn-1. Здійснюючи зворотний підстановку, далі послідовно знаходимо xn-1, xn-2, ..., x1. Обчислення невідомих тут проводяться за формулами
xn = bn (n-1) / ann (n-1),
xk = (bn (k-1) - ak, k +1 (k-1) xk +1 - akn (k-1) xn) / akk (k-1), (k = n - 1,, 1) .
Зауважимо, що обчислення множників, а також зворотна підстановка вимагають поділу на головні елементи akk (k-1). Тому якщо один з головних елементів виявляється рівним нулю, то схема єдиного ділення не може бути реалізована. Здоровий глузд підказує, що і в ситуації, коли всі головні елементи відмінні від нуля, але серед них є близькі до нуля, можливий неконтрольований ріст похибки.
2.2 Метод Гаусса з вибором головного елемента по стовпцю
На k-му кроці прямого ходу методу Гаусса з вибором головного елемента по стовпцю коефіцієнти рівнянь системи з номерами i = k + 1, ..., n перетворюються за формулами
aij (k) = aij (k-1) - qikakj, bi (k) = bi (k-1) - qikbk (k-1), i = k + 1, ..., n.
Інтуїтивно ясно, що для уникнення сильного зростання коефіцієнтів системи та пов'язаних з цим помилок не можна допускати появи великих множників qik.
У методі Гаусса з вибором головного елемента по стовпцю гарантується, що
| Qik | ≤ 1 для всіх k = 1, 2, ..., n - 1 і i = k + 1, ..., n.
Відмінність цього варіанту методу Гауса від схеми єдиного поділу полягає в тому, що на k-му кроці виняток як головного елемента вибирають максимальний за модулем коефіцієнт aikk за невідомої xk в рівняннях з номерами i = k + 1, ..., n. Потім відповідне обраному коефіцієнту рівняння з номером ik міняють місцями з k-м рівнянням системи для того, щоб головний елемент зайняв місце коефіцієнта akk (k-1). Після цієї перестановки виняток невідомого xk виробляють, як у схемі єдиного ділення.
3 Функціональні моделі та блок-схеми виконання завдання
Блок-схема рішення задачі представлена на малюнку 1.
Умовні позначення:
K - розмірність матриці;
MATRIX - матриця;
N - розмірність матриці;
X - матриця рішення СЛАР;
I _ MAX - індекс максимального елемента в рядку;
J _ MAX - індекс максимального елемента в стовпці;
OTV - масив позицій елементів;
RES - допоміжний масив;
TEMP - тимчасова змінна;
GLAV _ EL - функція, що визначає на якій позиції повинен стояти головний елемент;
INDEX - робоча змінна.
Рисунок 1 - Блок-схема рішення задачі для функції GAUSS
\
4 Програмна реалізація рішення задачі
ФУНКЦІЯ ПОШУКУ МАКСИМАЛЬНОГО ЕЛЕМЕНТА і перестановки рядків і стовпців
(DEFUN GLAV_EL (K MATRIX NX)
(DECLARE (SPECIAL I_MAX))
(DECLARE (SPECIAL J_MAX))
(DECLARE (SPECIAL TEMP))
(DECLARE (SPECIAL I))
(SETQ I_MAX K)
(SETQ J_MAX K)
; ШУКАЄМО максимальний по модулю елемент
(DO
((IK))
((> = IN))
(DO
((JK))
((> = JN))
(IF (<(ABS (AREF MATRIX I_MAX J_MAX)) (ABS (AREF MATRIX IJ)))
(PROGN
(SETQ I_MAX I)
(SETQ J_MAX J)
)
)
(SETQ J (+ J 1))
)
(SETQ I (+ I 1))
)
; Переставляти РЯДКИ
(DO
((JK))
((> = J (+ N 1)))
(SETQ TEMP (AREF MATRIX KJ))
(SETF (AREF MATRIX KJ) (AREF MATRIX I_MAX J))
(SETF (AREF MATRIX I_MAX J) TEMP)
(SETQ J (+ J 1))
)
; Переставляти СТОВПЧИКУ
(DO
((I 0))
((> = IN))
(SETQ TEMP (AREF MATRIX IK))
(SETF (AREF MATRIX IK) (AREF MATRIX I J_MAX))
(SETF (AREF MATRIX I J_MAX) TEMP)
(SETQ I (+ I 1))
)
; ВРАХОВУЄМО ЗМІНА Я живий КОРЕНІВ
(SETQ I (AREF XK))
(SETF (AREF XK) (AREF X J_MAX))
(SETF (AREF X J_MAX) I)
)
(DEFUN GAUSS (MATRIX NX)
(DECLARE (SPECIAL OTV))
(DECLARE (SPECIAL RES))
(SETQ OTV (MAKE-ARRAY 50: ELEMENT-TYPE 'INTEGER: INITIAL-ELEMENT 0))
(SETQ RES (MAKE-ARRAY N: ELEMENT-TYPE 'INTEGER: INITIAL-ELEMENT 0))
; СПОЧАТКУ ВСІ КОРЕНІ ПО ПОРЯДКУ
(DO
((I 0))
((> = I (+ N 1)))
(SETF (AREF OTV I) I)
(SETQ I (+ I 1))
)
; ПРЯМОЇ ХІД Метод Гауса
(DO
((K 0))
((> = KN))
; ВИЗНАЧАЄМО НА БУДЬ ПОЗИЦІЇ ПОВИНЕН СТОЯТИ ГОЛОВНИЙ ЕЛЕМЕНТ
(GLAV_EL K MATRIX N OTV)
(IF (<(ABS (AREF MATRIX KK)) 0.0001) (PRINT "SYSTEMA NE IMEET EDINSTVENNOGO RESHENIYA"))
(DO
((JN))
((<JK))
(SETF (AREF MATRIX KJ) (FLOAT (/ (AREF MATRIX KJ) (AREF MATRIX KK))))
(SETQ J (- J 1))
)
(DO
((I (+ K 1)))
((> = IN))
(DO
((JN))
((<JK))
(SETF (AREF MATRIX IJ) (- (AREF MATRIX IJ) (* (AREF MATRIX KJ) (AREF MATRIX IK))))
(SETQ J (- J 1))
)
(SETQ I (+ I 1))
)
(SETQ K (+ K 1))
)
; ЗВОРОТНИЙ КОД
(DO
((I 0))
((> = IN))
(SETF (AREF XI) (AREF MATRIX IN))
(SETQ I (+ I 1))
)
(DO
((I (- N 2)))
((<I 0))
(DO
((J (+ I 1)))
((> = JN))
(SETF (AREF XI) (- (AREF XI) (* (AREF XJ) (AREF MATRIX IJ))))
(SETQ J (+ J 1))
)
(SETQ I (- I 1))
)
(DO
((I 0) (INDEX 0))
((> = IN) RES)
(DO
((J 0))
((> = JN))
; Розставляємо КОРЕНІ ПО ПОРЯДКУ
(IF (= I (AREF OTV J))
(PROGN
(SETF (AREF RES INDEX) (AREF XJ))
(SETQ INDEX (+ INDEX 1))
)
)
(SETQ J (+ J 1))
)
(SETQ I (+ I 1))
)
(SETQ X RES)
)
(SETQ INPUT_STREAM (OPEN "D: \ GAUSS_MATRIX.TXT": DIRECTION: INPUT))
; ОТРИМУЄМО РОЗМІРНІСТЬ МАТРИЦІ
(SETF N (READ INPUT_STREAM))
; ОТРИМУЄМО МАТРИЦЯ
(SETF MATRIX (READ INPUT_STREAM))
(CLOSE INPUT_STREAM)
(SETQ X (MAKE-ARRAY 50: ELEMENT-TYPE 'INTEGER: INITIAL-ELEMENT 0))
(SETQ RES (GAUSS MATRIX NX))
; ЗАПИСУЮТЬ КОРЕНІ СЛАР У ФАЙЛ
(SETQ OUTPUT_STREAM (OPEN "D: \ KORNI_SLAY.TXT": DIRECTION: OUTPUT))
(PRINT RES OUTPUT_STREAM)
(TERPRI OUTPUT_STREAM)
(CLOSE OUTPUT_STREAM)
5 Приклад виконання програми
Приклад 1.
Рисунок 2 - Вхідні дані
Рисунок 3 - Вихідні дані
Приклад 2.
Рисунок 4 - Вхідні дані
Малюнок 5 - Вихідні дані
Приклад 3.
Малюнок 6 - Вхідні дані
Малюнок 7 - Вихідні дані
ВИСНОВОК
Проблема підвищення якості обчислень, як невідповідність між бажаним і дійсним, існує і буде існувати надалі. Її вирішення сприятиме розвиток інформаційних технологій, яке полягає як в удосконаленні методів організації інформаційних процесів, так і їх реалізації за допомогою конкретних інструментів - середовищ і мов програмування.
Підсумком роботи можна вважати створену функціональну модель чисельного рішення системи лінійних рівнянь за допомогою методу виключення Гауса з вибором головного елемента по стовпцю. Створена функціональна модель і її програмна реалізація можуть служити органічною частиною вирішення більш складних завдань.
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ та літератури
Бронштейн, І.М. Довідник з математики для інженерів і учнів втузів [Текст] / І.М. Бронштейн, К.А. Семендяев. - М.: Наука, 2007. - 708 с.
Васильєв, Ф.П. Чисельні методи розв'язання екстремальних задач. [Текст] / Ф.П. Васильєв - М.: Наука, 2002. C. 415.
Вища документація - Online документація [Електронний ресурс] - Режим доступу: http://vm.psati.ru/online-vmath/index.php?page=8
Каліткін, М.М. Чисельні методи. [Електронний ресурс] / М.М. Каліткін. - М.: Питер, 2001. С. 504.
Кнут, Д.Е. Мистецтво програмування. Основні алгоритми [Текст] / Д.Е. Батіг. - М.: Вільямс, 2007. Т.1 .- 712 с.
Метод Гауса [Електронний ресурс] - Режим доступу: http: / / www. Wikipedia. Org / wiki / Метод_Гаусса.
Сіманков, В.С. Основи функціонального програмування [Текст] / В.С. Сіманков, Т.Т. Зангієв, І.В. Зайцев. - Краснодар: КубГТУ, 2002. - 160 с.
Степанов, П.А. Функціональне програмування мовою Lisp. [Електронний ресурс] / П. А. Степанов, А.В. Бржезовскій. - М.: ГУАП, 2003. С. 79.
Хювенен Е. Світ Ліспу [Текст] / Е. Хювенен, Й. Сеппянен. - М.: Світ, 1990. - 460 с.