2. Решение системы линейных алгебраических уравнений

Система уравнений с неизвестными: .

Один из способов решения СЛАУ – метод последовательной подстановки:

Такая процедура хорошо работает, но здесь производится очень много алгебраических преобразований, в которые легко может вкрастся ошибка. При возрастании числа уравнений и неизвестных время на выполнение этих преобразований быстро растет.

Метод Жордана-Гаусса. СЛАУ можно представить матрицей с строками и столбцами:

Со строками матрицы можно выполнить некоторые преобразовавния, которые приведут к следующему результату:

.

Пример.

.

Делим первую строку на ее первый элемент, затем подбираем для нее коэффициенты таким образом, чтобы при умножении на коэффициент и сложении с ккакой-либо из оставшихся строк элементы первого столбца обнулялись

.

Повторим эти действия для второй строки.

Для итерационных методов решения операций меньше, но нужно выполнить условия сходимости итерационного процесса. Рассмотрим метод простой итерации

Вопросы

1. Какие алгоритмы называются численными?

2. Схемы вычисления значения многочлена, их сравнение, преимущества и недостатки каждой.

3. Какие из арифметических операций являются предпочтительными при оценке вычислительной сложности алгоритма? Почему?

4. Методы решения систем линейных алгебраических уравнений, сравнение их вычислительных сложностей.

Литература

1. Деммель Дж. Вычислительная линейная алгебра / Дж.Деммель; пер.с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 430 с.

2. Бахвалов Н.С. Численные методы / Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков. — М.: БИНОМ. Лаборатория знаний, 2006. — 636 с.

3. Каханер Д. Численные методы и программное обеспечение / Д.Каханер, К.Моулер, С.Нэш; пер. с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 575 с.

4. Воеводин В.В. Вычислительные основы линейной алгебры / В.В.Воеводин. — М.: Наука. Гл.ред.физ.-мат.лит., 1977. — 304 с.

Семестровий модуль 2. АНАЛИЗ ПОСЛЕДОВАТЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ ИСПОЛЬЗОВАНИЯ В ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

Лекция 8. Граф информационной зависимости реализации алгоритма – основной способ представления алгоритма для выявления внутреннего параллелизма

План

1. Цели анализа последовательных алгоритмов

2. Основы построения графа алгоритма

3. Допустимые преобразования алгоритма

1. Цели анализа последовательных алгоритмов

Появление параллельных вычислительных систем и внедрение их в практику решения больших прикладных задач привело к возникновению целого ряда проблем в области численного программного обеспечения. Построение новых численных методов для параллельных вычислительных систем процесс долговременный и сложный. Попытки разработать специальные параллельные методы не всегда оказывались состоятельными [1]. Кроме того, непростительно просто отбросить при работе на параллельных ЭВМ огромный багаж численных методов и программ, накопленный в процессе длительного использования последовательных компьютеров. Актуальны не только исследования “классических” последовательных алгоритмов для определения возможности их использования в параллельных вычислительных системах, но и сведения о параллельных свойствах алгоритмов, а также знания, позволяющие эти сведения получать.

Эффективное использование различного типа параллельных вычислительных систем возможно за счет одновременного выполнения ими ветвей вычислений, не связанных между собой информационно. Поэтому целью исследования последовательного алгоритма является поиск и выделение таких ветвей. Если они найдены, говорят, что алгоритму присущ внутренний параллелизм, и его принципиально возможно реализовать на параллельной вычислительной системе, в противном случае его использование в ней нецелесообразно.

Одной из возможных форм записи алгоритмов является их представление в виде графов (грубо говоря, любая блок-схема алгоритма также может с определенными оговорками рассматриваться как граф) [2].