Якщо в матриці є нульова рядок, то всі рядки нижче неї також нульові; інформатика,
Пошук рішень системи лінійних рівнянь методом Гаусса
1. якщо в матриці є нульова рядок, то всі рядки нижче неї також нульові;
2. нехай aij нерівний 0 - перший ненульовий елемент в рядку з індексом i, тобто елементи ail = 0 при l Ступінчаста матриця виглядає так: Тут темними квадратиками відзначені перші ненульові елементи рядків матриці. Білим кольором зображуються нульові елементи, сірим кольором - довільні елементи. Алгоритм Гауса використовує елементарні перетворення матриці двох типів. · Перетворення першого роду: два рядки матриці міняються місцями, і при цьому знаки всіх елементів однієї з рядків змінюються на протилежні. · Перетворення другого роду: до одного рядка матриці додається інший рядок, помножена на довільне число. Елементарні перетворення зберігають визначник і ранг матриці, а також безліч рішень лінійної системи. Алгоритм Гауса призводить довільну матрицю елементарними перетвореннями до ступінчастого вигляду. Для ступінчастою квадратної матриці визначник дорівнює добутку діагональних елементів, а ранг - числу ненульових рядків (рангом за визначенням називається розмірність лінійної оболонки рядків матриці). Метод Гаусса в математичному варіанті полягає в наступному: 1. шукаємо спочатку ненульовий елемент в першому стовпці. Якщо всі елементи першого стовпчика нульові, то переходимо на дві колонки, і так далі. Якщо знайшли ненульовий елемент в k-му рядку, то за допомогою елементарного перетворення першого роду міняємо місцями першу і k-ю рядки, домагаючись того, щоб перший елемент першого рядка був відмінний від нуля; 2. за допомогою елементарні перетворення другого роду, Обнуляємо всі елементи першого стовпчика, починаючи з другого елементу. Для цього від рядка з номером k віднімаємо перший рядок, помножену на коефіцієнт ak1 / a11. 3. переходимо на дві колонки (або j-му, якщо всі елементи першого стовпчика були нульовими), і в подальшому розглядаємо тільки частина матриці, починаючи з другого рядка і нижче. Знову повторюємо пункти 1) і 2) до тих пір, поки не приведемо матрицю до ступінчастого вигляду. Програмістський варіант методу Гаусса має три відмінності від математичного: 1. індекси рядків і стовпців матриці починаються з нуля, а не з одиниці; 2. недостатньо знайти просто ненульовий елемент в стовпці. У програмуванні всі дії з числами виробляються наближено, тому можна вважати, що точного рівності дійсних чисел взагалі не буває. Деякі компілятори навіть видають попередження на кожну операцію перевірки рівності дійсних чисел. Тому замість перевірки на рівність нулю числа aij слід порівнювати його абсолютну величину ij # 8204; з дуже невеликою кількістю # 949; (Наприклад, # 949; = 0.00000001). якщо ij # 8204; =<ε, то следует считать элемент aij нулевым; 3. при обнулення елементів j-го стовпчика, починаючи з рядка i + 1, ми до k-му рядку, де k> i, додаємо i-й рядок, помножену на коефіцієнт r = -akj / aij: Така схема працює нормально тільки тоді, коли коефіцієнт r по абсолютній величині не перевищує одиниці. В іншому випадку, помилки округлення множаться на великий коефіцієнт і, таким чином, експоненціально зростають. Математики називають це явище нестійкістю обчислювальної схеми. Якщо обчислювальна схема нестійка, то отримані з її допомогою результати не мають ніякого відношення до вихідної задачі. У нашому випадку схема стійка, коли коефіцієнт r = -akj / aij не перевищує по модулю одиниці. Для цього має виконуватися нерівність Звідси випливає, що при пошуку дозволяє елемента в j-му стовпці необхідно знайти не перший-ліпший ненульовий елемент, а максимальний за абсолютною величиною. Якщо він по модулю не перевищує # 949 ;, то вважаємо, що всі елементи стовпця нульові; інакше міняємо місцями рядки, ставлячи його на вершину стовпчика, і потім Обнуляємо стовпець елементарними перетвореннями другого роду. Основна ідея методу Гаусса- привести матрицю систему до діагонального вигляду, тобто всі елементи головної діагоналі -нулі. Для приведення матриці до такого виду, ми вибираємо самий верхній рядок матриці, і віднімаємо її з усіх інших рядків, помноживши її для кожного рядка на якийсь коефіцієнт, так, що самий лівий стовпець нижче головної діагоналі заповнений нулями. Віднімається з коефіцієнтом рядок називається поточним рядком. Вибираючи поточний рядок спочатку верхню, а потім все нижче і нижче, ми доб'ємося, що всі елементи нижче головної діагоналі буде дорівнювати нулю. Цю частину метода- обробка рядків по поточному рядку і належить распараллеливать. Суть методу полягає в послідовному виключенні невідомих. Розглянемо систему лінійних рівнянь: Розділимо обидві частини 1-го рівняння на a11 # Шістьдесят одна тисяча шістсот двадцять-п'ять; 0, потім: 1) помножимо на а21 і віднімемо з другого рівняння 2) помножимо на а31 і віднімемо з третього рівняння і т.д. Отримаємо. де d1j = a1j / a11. j = 2, 3, ..., n + 1. dij = aij - ai1 d1j i = 2, 3, .... n; j = 2, 3, .... n + 1. Далі повторюємо ці ж дії для другого рівняння системи, потім - для третього і т.д. Приклад. Вирішити систему лінійних рівнянь методом Гаусса. Складемо розширену матрицю системи. Таким чином, вихідна система може бути представлена у вигляді: , Приклад. Вирішити систему методом Гаусса. Складемо розширену матрицю системи. Таким чином, вихідна система може бути представлена у вигляді: . звідки отримуємо: z = 3; y = 2; x = 1. Робота з файлами. Стандартна бібліотека С ++ містить набір функцій для роботи з файлами. Ці функції описані в стандарті ANSI. Відзначимо, що файловий ввід-висновок не є частиною мови С +, і ANSI-функції - не єдиний засіб введення-виведення. Так, в операційній системі Unix більш популярний інший набір функцій вводу-виводу, який можна використовувати не тільки для роботи з файлами, але і для обміну по мережі. У C ++ часто використовуються бібліотеки класів для введення-виведення. Проте, функції ANSI-бібліотеки підтримуються всіма С ++ - компіляторами, і тому програми, які застосовують їх, легко переносяться з однієї платформи на іншу. Прототипи функцій вводу-виводу і використовуються для цього типи даних описані в стандартному заголовному файлі "stdio.h. Відкриття файлу: функція fopen. Для доступу до файлу застосовується тип даних FILE. Це структурний тип, ім'я якого задано за допомогою оператора typedef в стандартному заголовному файлі "stdio.h". Програмісту не потрібно знати, як влаштована структура типу файл: її пристрій може бути системно залежним, тому з метою переносимості програм звертатися явно до полів структури FILE заборонено. Тип даних "покажчик на структуру FILE використовується в програмах як чорний ящик: функція відкриття файлу повертає цей покажчик в разі успіху, і в подальшому все файлові функції застосовують його для доступу до файлу. Тут path - шлях до файлу (наприклад, ім'я файлу або абсолютний шлях до файлу), mode - режим відкриття файлу. Рядок mode може містити кілька букв. Буква "r" (від слова read) означає, що файл відкривається для читання (файл повинен існувати). Буква "w" (від слова write) означає запис в файл, при цьому старе вміст файлу втрачається, а в разі відсутності файлу він створюється. Буква "a" (від слова append) означає запис в кінець існуючого файлу або створення нового файлу, якщо файл не існує. У деяких операційних системах є відмінності в роботі з текстовими і бінарними файлами (до таких систем відносяться MS DOS і MS Windows; в системі Unix відмінностей між текстовими та бінарними файлами немає). У таких системах при відкритті бінарного файлу до рядка mode слід додавати букву "b" (від слова binary), а при відкритті текстового файлу - букву "t" (від слова text). Крім того, при відкритті можна дозволити виконувати як операції читання, так і запису; для цього використовується символ + (плюс). Порядок букв в рядку mode наступний: спочатку йде одна з букв "r", "w", "a", потім в довільному порядку можуть йти символи "b", "t", "+". Букви "b" і "t" можна використовувати, навіть якщо в операційній системі немає відмінностей між бінарними і текстовими файлами, в цьому випадку вони просто ігноруються. 3.Описание алгоритму рішення СЛАР методом Гауса Скласти програму рішення систем лінійних алгебраїчних рівнянь з матрицею порядку n методом Гаусса з використанням мови С ++. Алгоритм рішення системи лінійних рівнянь за допомогою методу Гаусса. Алгоритм реалізований на мові С ++. Нехай у нас є система N лінійних рівнянь де xi - невідомі, aij - коефіцієнти при невідомих, bi - вільні члени в рівняннях, i, j пробігають значення від 1 до N. Суть методу Гаусса полягає в тому, що за допомогою деяких операцій вихідну систему рівнянь можна звести до більш простій системі. Ця проста система має трикутний вигляд: Особливість цієї системи - в рядках з номером i все коефіцієнти aij при j
Якщо ми змогли привести нашу систему рівнянь до такого трикутного вигляду, то вирішити рівняння вже просто. З останнього рівняння знаходимо xN = bN / aNN. Далі підставляємо його в передостаннє рівняння і знаходимо з нього xN-1. Підставляємо обидва знайдених рішення в наступне з кінця рівняння і знаходимо xN-2. І так далі, поки не знайдемо x1. на чому рішення закінчується. Така процедура називається зворотної прогоном. Тепер перейдемо до питання як же домогтися того, щоб система стала трикутної. З лінійної алгебри відомо що якщо до деякої рядку системи рівнянь додати будь-яку лінійну комбінацію будь-яких інших рядків цієї системи, то рішення системи не зміниться. Під лінійною комбінацією рядків розуміється сума рядків, кожна з яких множиться на деяке число (в принципі, будь-який). Потрібно, щоб у другому рядку вийшло рівняння, в якій відсутній член при x1. Додамо до цього рядка перший рядок, помножену на деяке число M. Для того, щоб член при x1 дорівнював нулю, потрібно, щоб M = - a21 / a11. Виконавши цю операцію, вийшло рівняння запишемо замість другого і приступимо до третього рівняння. До нього ми додамо перше рівняння, помножене на M = - a31 / a11 і теж отримаємо нуль замість члена при x1. Таку операцію потрібно виконати над усіма іншими рівняннями. В результаті отримаємо систему такого виду: Після цього будемо позбуватися від членів при x2 в третьому, четвертому, N-му рівнянні. Для цього потрібно до рівняння з j-м номером додати 2-е рівняння, помножене на M = - aj2 / a22. Виконавши цю операцію над усіма іншими рівняннями, отримаємо систему де немає членів з x2 в рівняннях з номером більше 2. І так далі. Проробивши це для третього члена, четвертого. до тих пір, поки не закінчаться рівняння, отримаємо в підсумку систему трикутного виду. Алгоритм описаний в псевдокоді (команди у вигляді тексту російською мовою). ПРОЦЕС 0: (головний процес) 1.Разослать всім процесам кількість поточних рядків. (Або не всім процесам, якщо процесів більше ніж рядків). 2.ЦІКЛ по рядку (вибір поточного рядка) 1.Разослать всім процесам поточний рядок. (Якщо число процесів більше ніж залишилося рядків для обробки (рядків нижче поточного рядка), то розіслати поточну рядок не всім процесам, а тільки тим, які будуть задіяні в обробці рядків.) 2.Разослать всім процесам рядки для обробки (посилаємо рядок, потім рядки в матриці). Розділити між процесами рядки нижче поточної. Поділяємо так в циклі по рядках роздаємо по одній кожному процесу, поки не закінчаться строки, по процесам 1..N йдемо циклічно. 3.Разослать всім процесам кількості рядків, які були надіслані їм для обробки. 4.Прінять від процесів 1..N оброблені рядки, занести їх в матрицю. (Приймаємо рядок і номер рядка в матриці) 5.Вибрать наступну поточну рядок - новий крок циклу. 3.Вичісліть рішення системи по діагональної матриці. 4.Видать результат роботи. 1.Прінімаем кількість поточних рядків. 2.ЦІКЛ ОБРОБКИ ОТРИМАНИХ СТРОК 1.Прінімаем повідомлення про кількість рядків для обробки 2.Якщо число рядків для обробки> 0 то: 1.Прінімаем повідомлення з поточним рядком 2.ЦІКЛ обробки рядків 1.Прінімаем з поміткою для обробки. (Отримуємо ще номер рядка в матриці). 2.Обрабативаем отриманий рядок 3.Посилаем головному процесу результати роботи. Для кожного рядка посилаємо рядок і номер рядка. 4.Ідём на новий крок циклу обробки рядків. 4.Ісходний текст програми Скласти програму рішення систем лінійних алгебраїчних рівнянь з квадратною невиродженою матрицею порядку n методом Гаусса з використанням мови С ++. // Рішення системи лінійних рівнянь методом Гаусса. В результаті виконання курсового проекту були розроблені два класи функцій для вирішення найпростіших завдань лінійної алгебри. Число цих функцій порівняно невелика, проте можна легко додати в ці класи більш складні функції, побудовані на базі вже наявних. Класи дозволяють працювати з матрицями і векторами, елементи яких можуть бути будь-якого типу, проте на практиці найчастіше використовується цілий тип і тип чисел з плаваючою комою. Класи написані на мові С ++, проте можуть бути легко переписані на будь-якому з сучасних мов програмування, так як наведені досить прості алгоритми всіх компонентних функцій. Були максимально передбачені всілякі помилки, які можуть виникнути при використанні функцій даних класів. Особлива увага приділялася розумного виділенню пам'яті подоб'екти під час виконання програми, тому всі функції були ретельно отлажени.Класси Matrix і Vector можуть бути ефективно застосовані на практиці в задачах, що потребують операцій з матрицями і векторами, а також пов'язаних з рішенням систем лінійних алгебраїчних рівнянь. 3. Введення в мову С ++: Підручник. / Бьярн Страустрап. 9. МОДЕЛІ І Cтруктура ДАНИХ: / Навчальний посібник / Пошук рішень системи лінійних рівнянь методом Гаусса Інформація про роботу «Пошук рішень системи лінійних рівнянь методом Гаусса»
трикутною матрицею. Обчислення значень невідомих виробляють на етапі зворотного ходу. Метою даної курсової роботи є чисельне рішення системи лінійних рівнянь за допомогою методу виключення Гауса з вибором головного елемента по стовпцю. 1 Постановка завдання Завдання ставиться так. Нехай потрібно знайти рішення системи лінійних алгебраїчних рівнянь a1,1x1 + a1.
1.2 0.4 -0.8 -0.8 3.6 4 4.7 10.4 9.7 9.7 -8.4Результат обчислень за методом Гаусса x1 = 5.0000000000E +00 x2 = -4.0000000000E +00 x3 = 3.0000000000E +00 x4 = -2.0000000000E +00 2.2 Програма рішення систем лінійних рівнянь методом Зейделя 2.2.1. Постановка задачі. Потрібно вирішити систему лінійних алгебраїчних рівнянь з речовими коефіцієнтами виду a11x1 + a12x2 + ... + a1nxn =.