дипломы,курсовые,рефераты,контрольные,диссертации на заказ
 

Алгоритм нахождения решений произвольной системы линейных уравнений (метод Гаусса)

Пусть дана система $ m$ линейных уравнений с $ n$ неизвестными $ {Ax=b}$ . Требуется найти ее общее решение, если она совместна, или установить ее несовместность. Метод, который будет изложен в этом разделе, близок к методу вычисления определителя 5.1.с и к методу нахождения ранга матрицы (раздел 5.8). Предлагаемый алгоритм называется методом Гаусса или методом последовательного исключения неизвестных.

Выпишем расширенную матрицу системы

$\displaystyle A^*=\left(\begin{array}{ccccc}a_{11}&a_{12}&\dots&a_{1n}&b_1\\ ... ...{2n}&b_2\\ \hdotsfor{5}\\ a_{m1}&a_{m2}&\dots&a_{mn}&b_m\end{array}\right).$

Назовем элементарными операциями следующие действия с матрицами:

  1. перестановка строк;
  2. умножение строки на число, отличное от нуля;
  3. сложение строки с другой строкой, умноженной на число.

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

Читатель легко проверит, что если по матрице, полученной из $ A^*$ выполнением элементарной операции, восстановить систему уравнений, то новая система будет равносильна исходной.

Цель алгоритма -- с помощью применения последовательности элементарных операций к матрице $ A^*$ добиться, чтобы каждая строка, кроме, быть может, первой, начиналась с нулей, и число нулей до первого ненулевого элемента в каждой следующей строке было больше, чем в предыдущей.

Шаг алгоритма заключается в следующем. Находим первый ненулевой столбец в матрице $ A^*$ . Пусть это будет столбец с номером $ i$ . Находим в нем ненулевой элемент и строку с этим элементом меняем местами с первой строкой. Чтобы не нагромождать дополнительных обозначений, будем считать, что такая смена строк в матрице $ A^*$ уже произведена, то есть $ {a_{1i}\ne0}$ . Тогда ко второй строке прибавим первую, умноженную на число $ \left(-\dfrac{a_{2i}}{a_{1i}}\right)$ , к третьей строке прибавим первую, умноженную на число $ \left(-\dfrac{a_{3i}}{a_{1i}}\right)$ , и т.д. В результате получим матрицу

$\displaystyle A^*_1=\left(\begin{array}{cccccccc}0&\dots&0&a_{1i}&a_{1i+1}&\dot... ...\\ 0&\dots&0&0&a_{mi+1}^{(1)}&\dots&a_{mn}^{(1)}&b_m^{(1)}\end{array}\right).$
(Первые нулевые столбцы, как правило, отсутствуют.)

Если в матрице $ A^*_1$ встретилась строка с номером $ k$ , в которой все элементы $ a_{kj}^{(1)}$ равны нулю, а $ {b_k^{(1)}\ne0}$ , то выполнение алгоритма останавливаем и делаем вывод, что система несовместна. Действительно, восстанавливая систему уравнений по расширенной матрице, получим, что $ k$ -ое уравнение будет иметь вид

$\displaystyle 0\cdot x_1+0\cdot x_2+\ldots0\cdot x_n=b_k^{(1)}.$
Этому уравнению не удовлетворяет ни один набор чисел $ {x_1,x_2,\dots,x_k}$ .

Матрицу $ A^*_1$ можно записать в виде

$\displaystyle A^*_1=\left(\begin{array}{ccc}{\begin{array}{ccc}0&\dots&0\end{ar... ...begin{array}{c}0\\ \vdots\\ 0\end{array}}&\mbox{\Huge\it B*}\end{array}\right),$
где
$\displaystyle B^*=\left(\begin{array}{ccccc} a_{2i+1}^{(1)}&a_{2i+2}^{(1)}&\do... ... a_{mi+1}^{(1)}&a_{mi+2}^{(1)}&\dots&a_{mn}^{(1)}&b_m^{(1)}\end{array}\right).$
По отношению к матрице $ B^*$ выполняем описанный шаг алгоритма. Получаем матрицу
$\displaystyle B_1^*=\left(\begin{array}{cccccccc} 0&\dots&0&a_{2j}^{(2)}&a_{2j... ...\\ 0&\dots&0&0&a_{mj+1}^{(2)}&\dots&a_{mn}^{(2)}&b_m^{(2)}\end{array}\right),$
где $ j>i$ , $ a_{2j}^{(2)}\ne0$ . Эту матрицу снова можно записать в виде
$\displaystyle B^*_1=\left(\begin{array}{ccc}{\begin{array}{ccc}0&\dots&0\end{ar... ...begin{array}{c}0\\ \vdots\\ 0\end{array}}&\mbox{\Huge\it C*}\end{array}\right),$
и к матрице $ C^*$ снова применим описанный выше шаг алгоритма.

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

Если бы мы не уменьшали матрицу, то в итоге пришли бы к матрице вида

$\displaystyle \tilde A^*=\left(\begin{array}{ccccccccccccc} 0&\dots&0&a_{1i}^{... ... \hdotsfor{13}\\ 0&\dots&0&0&\dots&0&0&\dots&0&0&\dots&0&0\end{array}\right).$
Свойства градиента и производной по направлению Криволинейный интеграл Первоначально функции управления системой коммутации возлагались на операторов.
Далее выполняется так называемый обратный ход метода Гаусса. По матрице $ \tilde A^*$ составляем систему уравнений. В левой части оставляем неизвестные с номерами, соответствующими первым ненулевым элементам в каждой строке, то есть $ {x_i,\,x_j,\,\dots,x_r}$ . Заметим, что $ {r={\rm Rg}A}$ . Остальные неизвестные переносим в правую часть. Считая неизвестные в правой части некоторыми фиксированными величинами, несложно выразить через них неизвестные левой части.

Теперь, придавая неизвестным в правой части произвольные значения и вычисляя значения переменных левой части, мы будем находить различные решения исходной системы $ {Ax=b}$ . Чтобы записать общее решение, нужно неизвестные в правой части обозначить в каком-либо порядке буквами $ {C_1,\,C_2,\dots,C_{n-r}}$ , включая и те неизвестные, которые явно не выписаны в правой части из-за нулевых коэффициентов, и тогда столбец неизвестных можно записать в виде столбца, где каждый элемент будет линейной комбинацией произвольных величин $ {C_1,\,C_2,\dots,C_{n-r}}$ (в частности, просто произвольной величиной $ C_k$ ). Эта запись и будет общим решением системы.

Если система была однородной, то получим общее решение однородной системы. Коэффициенты при $ C_1$ , взятые в каждом элементе столбца общего решения, составят первое решение из фундаментальной системы решений, коэффициенты при $ C_2$  -- второе решение и т.д.

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

        Замечание 15.4   У читателя может возникнуть вопрос: "Зачем рассматривать случай, когда некоторые столбцы матрицы $ A^*$ нулевые? Ведь в этом случае соответствующие им переменные в системе уравнений в явном виде отсутствуют." Но дело том, что в некоторых задачах, например, при нахождении собственных чисел матрицы, такие системы возникают, и игнорировать отсутствующие переменные нельзя, так как при этом происходит потеря важных для задачи решений.         
      

Непрерывность функции на интервале и на отрезке

 

  Определение 3.4   Назовём функцию $ f(x)$ непрерывной на множестве $ A\sbs\mathcal{D}(f)$, если
$ \forall\ x_0\in A\ \exists\ \lim\limits_{\mathcal{B}(x_0)^A}f(x)=f(x_0)).$     

Нетрудно видеть, что тогда при $ A=(a;b)$ и при $ A=[a;b]$ это определение совпадает с теми, что были выше даны специально для интервала и отрезка.

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

Поскольку непрерывность на интервале и отрезке определяется поточечно, имеет место теорема, которая является непосредственным следствием теоремы 3.1:

        Теорема 3.5   Пусть $ f(x)$ и $ g(x)$ -- функции и $ I$ -- интервал или отрезок, лежащий в $ \mathcal{D}(f)\cap\mathcal{D}(g)$. Пусть $ f$ и $ g$ непрерывны на $ I$. Тогда функции $ h_1(x)=f(x)+g(x)$, $ h_2(x)=f(x)-g(x)$, $ h_3(x)=f(x)g(x)$ непpеpывны на $ I$. Если вдобавок $ g(x)\ne0$ пpи всех $ x\in I$, то функция $ h_4(x)=\dfrac{f(x)}{g(x)}$ также непpеpывна на $ I$.     

Из этой теоpемы вытекает следующее утвеpждение, точно так же, как из теоpемы 3.1 -- пpедложение 3.3:

        Предложение 3.4   Множество $ \mathcal{C}_I$ всех функций, непpеpывных на интеpвале или отpезке $ I\sbs\mathbb{R}$ -- это линейное пpостpанство:
$\displaystyle f_1(x),f_2(x)\in\mathcal{C}_I;C_1,C_2=\mathrm{const}\quad\Longrightarrow \quad C_1f_1(x)+C_2f_2(x)\in\mathcal{C}_I.$
    

Более сложное свойство непрерывной функции выражает следующая теорема.

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

        Теорема 3.6 (о корне непрерывной функции)   Пусть функция $ f$ непрерывна на отрезке $ [a;b]$, причём $ f(a)$ и $ f(b)$ -- числа разных знаков. (Будем для определённости считать, что $ f(a)<0$, а $ f(b)>0$.) Тогда существует хотя бы одно такое значение $ x_0\in(a;b)$, что $ f(x_0)=0$ (то есть существует хотя бы один корень $ x_0$ уравнения $ f(x)=0$).

        Доказательство.     Рассмотрим середину отрезка $ c_1=\dfrac{a+b}{2}$. Тогда либо $ {f(c_1)=0}$, либо $ f(c_1)<0$, либо $ f(c_1)>0$. В первом случае корень найден: это $ x_0=c_1$. В остальных двух случаях рассмотрим ту часть отрезка, на концах которой функция $ f$ принимает значения разных знаков: $ [c_1;b]$ в случае $ f(c_1)<0$ или $ [a;c_1]$ в случае $ f(c_1)>0$. Выбранную половину отрезка обозначим через $ [a_1;b_1]$ и применим к ней ту же процедуру: разделим на две половины $ [a_1;c_2]$ и $ [c_2;b_1]$, где $ c_2=\dfrac{a_1+b_1}{2}$, и найдём $ f(c_2)$. В случае $ f(c_2)=0$ корень найден; в случае $ f(c_2)<0$ рассматриваем далее отрезок $ [a_2;b_2]=[c_2;b_1]$, в случае $ f(c_2)>0$ -- отрезок $ [a_2;b_2]=[a_1;c_2]$ и т. д.

Неопределенный интегралВекторное произведение векторов

Трассировка пиксельных изображений Adobe Illustrator Линейные блоковые коды