Вычислительные алгоритмы в инженерных задачах

ВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ В ИНЖЕНЕРНЫХ ЗАДАЧАХ Преподаватель: Егорова Наталья Николаевна каф. «АСиЦТ» Ауд. 2.359 Вы числительны е алгоритмы в инженерны х задачах — дисциплина, рассматривающая применение математических методов и алгоритмов в других областях науки и практики. Примерами такого применения будут: • численные методы (вычислительные методы), • линейное программирование, • оптимизация и исследование операций, • теория вероятностей и статистика, • теория информации, • теория игр, • финансовая математика, • криптография, • комбинаторика Математические методы и алгоритмы применяются к широкому классу прикладных задач путем составления математических моделей. Моделирование – это метод изучения сложного объекта путем его замены более удобным для исследования объектом, сохраняющим существенные черты изучаемого объекта, а также процесс построения замещающего объекта. Математическая модель – это знаковая модель исследуемой системы, составленная на языке математики. Многие задачи исследования различных объектов, систем, явлений приводят к необходимости решения: нелинейных уравнений с одним неизвестным, систем линейных и нелинейных уравнений, обыкновенных дифференциальных уравнений (ОДУ), систем ОДУ. Как показывает практика не все задачи имеют аналитическое решение. Поэтому на практике применяются численные методы решения. Многие задачи исследования различных объектов, систем, явлений приводят к необходимости решения: • • • • нелинейных уравнений с одним неизвестным, систем линейных и нелинейных уравнений, обыкновенных дифференциальных уравнений (ОДУ), систем ОДУ. Как показывает практика не все задачи имеют аналитическое решение. Поэтому на практике применяются численные методы решения. Виды численны х методов: Прямы е – решение получают за конечное число арифметических действий. Итерационны е – точное решение может быть получено теоретически в виде предела бесконечной сходящейся последовательности вычислений. Вероятностны е – методы случайного поиска решения. Примечание: Все виды численных методов позволяют получить только приближенное решение задачи, то есть численное решение всегда содержит погрешность . Решение систем линейны х уравнений Система m линейны х уравнений с n неизвестны ми — это система уравнений вида: (1) Здесь x1, x2, …, xn — неизвестные, которые надо определить. a11, a12, …, amn — коэффициенты системы b1, b2, … bm — свободные члены. Система называется однородной, если все её свободные члены равны нулю (b1 = b2 = … = bm = 0), иначе — неоднородной. Система называется квадратной, если число m уравнений равно числу n неизвестных. Решение системы — совокупность n чисел c1, c2, …, cn, таких что подстановка каждого ci вместо xi в систему (1) обращает все её уравнения в тождества. Система называется совместной, если она имеет хотя бы одно решение, и несовместной, если у неё нет ни одного решения. Совместная система вида (1) может иметь одно или более решений. Совместная система вида (1) называется определённой, если она имеет единственное решение; Если же у системы есть хотя бы два различных решения, то она называется неопределённой. Если уравнений больше, чем неизвестных, система называется переопределённой. Система линейных уравнений может быть представлена в матричной форме : или: AX = B Если к матрице А приписать справа столбец свободных членов, то получившаяся матрица называется расширенной. Методы решения Прямые (или точные) методы, позволяют найти решение за определённое количество шагов. Итерационные методы, основаны на использовании повторяющегося процесса и позволяют получить решение в результате последовательных приближений. методом Гаусса Теорема: Любую матрицу путём элементарных преобразований только над строками можно привести к ступенчатому виду. Алгоритм Алгоритм решения методом Гаусса подразделяется на два этапа. 1. На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме. Либо устанавливают, что система несовместна. 2. На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Пример Покажем, как методом Гаусса можно решить следующую систему:  2 x  y  z 8   3x  y  27  11   2 x  y  2 z  3  Обнулим коэффициенты при х во второй и третьей строчках. Для этого вычтем из них первую строчку, умноженную на и -1 , соответственно:  2 x  y  z 8  1 1 y  z 1  2 2  2 y  z 5  Теперь обнулим коэффициент при у в третьей строке, вычтя из неё вторую строку, умноженную на 4 :  2 x  y  z 8  1 1 y  z 1  2 2  2 y  z 5  В результате мы привели исходную систему к треугольному виду, тем самым закончив первый этап алгоритма. На втором этапе разрешим полученные уравнения в обратном порядке. Имеем: z=-1 из третьего; y=3 из второго, подставив полученное z. x=2 из первого, подставив полученные z и y. Таким образом исходная система решена. Метод Крамера Cпособ решения квадратных систем линейных алгебраических уравнений с ненулевым определителем основной матрицы (причём для таких уравнений решение существует и единственно). Описание метода: Для системы n линейных уравнений с n неизвестными: решение записывается в виде: i-ый столбец матрицы системы заменяется столбцом свободных членов. Реализация в Exsel: Матричны й метод Умножим это матричное уравнение слева на A - 1 т.е. на матрицу, обратную к матрице A: Реализация в Excel: Нажать (CTRL+Shift+Enter) Итерация для линейны х систем. Метод Якоби. Способ итераций дает возможность получить последовательность приближенных значений, сходящихся к точному решению системы. Для определенности ограничимся системой из четырех уравнений с четырьмя неизвестными (система четвертого порядка), которую запишем в виде: Разрешим первое уравнение системы относительно х1: a12 a13 a14 a15 x1  x2  x3  x4  a11 a11 a11 a11 Затем разрешим второе уравнение относительно х2 и т. д. Тогда систему можно переписать в виде: * 45 aik , где  ik  a ii i = 1, 2, 3, 4; k = 1, 2, 3, 4, 5. Зададим какие-либо начальные значения неизвестных (нулевые приближения): х1(0), х2(0), х3(0), х4(0). Подставляя эти значения в правые части системы (*), получим первые приближения х 1(1) , х 2(1) , х 3(1) , х 4(1) . Полученные первые приближения могут быть так же использованы для получения вторых, третьих и т. д. приближений. Т. е. можно записать:  x1( k ) x  2( k )   x 3( k )  x 4( k )  L1 ( x1( k  1) , x 2( k  1) , x3( k  1) , x 4 ( k  1) )  L2 ( x1( k  1) , x 2( k  1) , x3( k  1) , x 4 ( k  1) )  L3 ( x1( k  1) , x 2 ( k  1) , x3( k  1) , x 4 ( k  1) )  L4 ( x1( k  1) , x 2( k  1) , x3( k  1) , x 4 ( k  1) ) где Li линейная функция Условие окончания итерационного процесса при достижении заданной точности имеет вид: |xk+1-xk|<= Условия сходимости итерационного процесса. Для того чтобы итерационный процесс сходился к точному решению, достаточно, чтобы все коэффициенты системы были малы по сравнению с диагональными. n  ii   j 1,( j i ) ij , i 1, 2,..., n Пример: Рассмотрим систему линейных уравнений: Найти корни системы с погрешностью 0,005 Проверим условия сходимости: |а11|+|а22|+|а33|=4+8+5=17 Сумма модулей остальных коэффициентов 1+1+4+1+2=9 . Условие выполняется. Уравнения можно записать в виде: Начнем (х 1(0) , х 2(0) , х 3(0) ) = (0, 0, 0), Подставим х1 = 0, х2 = 0, х3 = 0 в правую часть каждого уравнения из системы (2), получим значения: 7   x1  4 1.75  21  x2  2.625  8  15  x3  3 5   Подставляем полученные значения в исходную систему и продолжаем процесс. В итоге итерация системы (2) сходится к решению (2, 3,998, 3). Оформление в Excel: Ответ: A3=(7+B2-C2)/4 D3=ABS(A3-A2) B3=(21+4*A2+C2)/8 E3=ABS(B3-B2) C3=(15+2*A2-B2)/5 F3=ABS(C3-D2) G3=ЕСЛИ(И(D3<=0,005;E3<=0,005;F3<=0,005);"корень";"-") Заполнив формулы, копируем 3 строку таблицы вниз, пока в столбце G не появиться слово «корень». Итерация Гаусса-Зейделя. Процесс итерации Якоби иногда можно модифицировать для ускорения сходимости. Процесс Якоби производит четыре последовательности: {х 1(k) }, { х 2(k) }, {х 3(k) } ,{x4(k)}. Подставим вычисленное х1(k) , в вычисление х2(k+1), x 3(k+1) Аналогично х 1(k+1) и х 2(k+1) можно использовать в вычислении х 3(k+1). Например, для уравнений из системы (1) это даст следующий вид итерационного процесса Гаусса-Зейделя  x1( k ) L1 ( x1( k  1) , x2( k  1) , x3( k  1) , x4( k  1) ) x  2( k ) L2 ( x1(k) , x2( k  1) , x3( k  1) , x4( k  1) )   x3( k ) L3 ( x1( k ) , x2( k ) , x3( k  1) , x4( k  1) )   x4( k ) L4 ( x1( k ) , x2( k ) , x3( k ) , x4( k  1) ) Оформление в Excel: A3=(7+B2-C2)/4 B3=(21+4*A3+C2)/8 C3=(15+2*A3-B3)/5 Метод сходится быстрей.