Чисельне рішення системи лінійних рівнянь за допомогою методу виключення Гауса з вибором головного елемента по стовпцю » Українські реферати

Теми рефератів

Авіація та космонавтика Банківська справа Безпека життєдіяльності Біографії Біологія Біологія і хімія Біржова справа Ботаніка та сільське гос-во Бухгалтерський облік і аудит Військова кафедра Географія

Геодезія Геологія Держава та право Журналістика Видавнича справа та поліграфія Іноземна мова Інформатика Інформатика, програмування Історія Історія техніки Комунікації і зв'язок Краєзнавство та етнографія Короткий зміст творів Кулінарія Культура та мистецтво Культурологія Зарубіжна література Російська мова Маркетинг Математика Медицина, здоров'я Медичні науки Міжнародні відносини Менеджмент Москвоведение Музика Податки, оподаткування Наука і техніка Решта реферати Педагогіка Політологія Право Право, юриспруденція Промисловість, виробництво Психологія Педагогіка Радіоелектроніка Реклама Релігія і міфологія Сексологія Соціологія Будівництво Митна система Технологія Транспорт Фізика Фізкультура і спорт Філософія Фінансові науки Хімія Екологія Економіка Економіко-математичне моделювання Етика Юриспруденція Мовознавство Мовознавство, філологія Контакти

Українські реферати та твори » Информатика, программирование » Чисельне рішення системи лінійних рівнянь за допомогою методу виключення Гауса з вибором головного елемента по стовпцю

Реферат Чисельне рішення системи лінійних рівнянь за допомогою методу виключення Гауса з вибором головного елемента по стовпцю

Категория: Информатика, программирование

ЗМІСТ

Введення

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-вектор правих частин.

Будемо вважати, що D = det A В№ 0 тобто рішення існує і єдино.

Розглянемо спочатку прямі методи. У явному вигляді рішення системи (1) записується у вигляді формул Крамера

x i = D i /D

де D 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 в усіх рівняннях, крім першого. В результаті отримаємо еквівалентну систему

a11x1 + a12x2 + a13x3 + ... + a1nxn = b1,

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.

В результаті отримаємо систему

a11x1 + a12x2 + a13x3 + a1nxn = b1,

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)