10993

Solution of Linear Algebraic Equations

Лекция

Математика и математический анализ

Lesson 6 3. Solution of Linear Algebraic Equations 3.1. Introduction A set of linear algebraic equations looks like this: 3.1 Here the n unknowns xj j = 1 2 n are related by m equations. The coefficients aij with i = 1 2 m and j = 1 2 n are known numbers as are the righthand side quantities bi i = 1 2 m. If n = m then there are as many equations as unknowns and there is a good chance of solving for a unique solution...

Английский

2013-04-03

132.5 KB

1 чел.

Lesson 6

3. Solution of Linear Algebraic Equations

3.1. Introduction

A set of linear algebraic equations looks like this:

  (3.1)

Here the n unknowns xj, j = 1; 2;; n are related by m equations. The coefficients aij with i = 1; 2;…; m and j = 1; 2;; n are known numbers, as are the right-hand side quantities bi , i = 1; 2;; m.

If n = m then there are as many equations as unknowns, and there is a good chance of solving for a unique solution set of xj’s. Analytically, there can fail to be a unique solution if one or more of the m equations is a linear combination of the others, a condition called row degeneracy, or if all equations contain certain variables only in exactly the same linear combination, called column degeneracy. (For square matrices, row degeneracy implies column degeneracy, and vice versa.)

Equations (3.1) can be written in matrix form as

     (3.2)

Here the raised dot denotes matrix multiplication, A is the matrix of coefficients, and b is the right-hand side written as a column vector,

 (3.3)

By convention, the first index on an element aij denotes its row, the second index its column.

If in matrix equation (3.2)

  (3.4)

then we have:

   (3.5)

Example 1

Consider the linear system:

Solve this system by formula (3.5):

This system may be solved by another direct method of linear algebra by Cramer’s Rule:

    (3.6)

In this case  is is determinant of a square matrix A in which
i - column is changed by a column vector b.

Example 2

This is Cramer's Rule applied to the above linear system:

We will consider the following tasks of computational linear algebra:

Solution of the matrix equation  for an unknown vector x, where A is a square matrix of coefficients, raised dot denotes matrix multiplication, and b is a known right-hand side vector.

Calculation of the matrix A-1 which is the matrix inverse of a square matrix A, i.e., A  A-1 = A-1· A = E, where E is the identity matrix (all zeros except for ones on the diagonal). This task is equivalent, for an matrix A, to the previous task with N different bj ’s (j = 1, 2,…, N), namely the unit vectors  (bj = all zero elements except for 1 in the j’th component). The corresponding x’s are then the columns of the matrix inverse of A.

Calculation of the determinant of a square matrix A.

There is also a great watershed dividing routines that are direct (i.e., execute in a predictable number of operations) from routines that are iterative (i.e., attempt to converge to the desired answer in however many steps are necessary). Iterative methods become preferable when the battle against loss of significance is in danger of being lost, either due to large N. We will treat iterative methods only incompletely in this book. These methods are important, but mostly beyond our scope. We will, however, discuss in detail a technique, which is on the borderline between direct and iterative methods, namely the iterative improvement of a solution that has been obtained by direct methods.

3.2. Gaussian Elimination with Backsubstitution

The usefulness of Gaussian elimination with backsubstitution is primarily pedagogical. It stands between full elimination schemes such as Gauss-Jordan, and triangular decomposition schemes. Gaussian elimination reduces a matrix not all the way to the identity matrix, but only halfway, to a matrix whose components on the diagonal and above (say) remain nontrivial. Let us now see what advantages accrues.

In Gaussian elimination, zeros are introduced below the diagonal element. Solve the following system of linear equations using Gauss elimination. For clarity, we will write out equations only for the case of four equations and four unknowns:

  (3.7)

The pivot element is a11 (a11 ≠ 0). The first equation is divided by the element a11 (a11 ≠ 0). This being a trivial linear combination of the first equation:

  (3.8)

where  .

We need to multiply the first equation (3.8) by a21, a31 and a41 and subtract from 2nd, 3rd and 4th equations so those zeros are introduced in the first position everywhere except the first equation. The modified system of linear equations is:

 (3.9)

In this system (3.9) the as do not have their original numerical values, but have been modified by all the equation operations in the elimination to this point:

 (3.10)

Now the pivot element is , then the first equation in (3.9) is divided by the pivot element:

 (3.11)

 (j =3, 4, 5).

Now we need to multiply the first equation (3.11) by  and  and subtract from 2nd and 3rd equations (3.9) so those zeros are introduced in the second position. The new linear system consists of the two equations:

 (3.12)

The pivot element of the new system is  If , the first equation (3.12) is divided by :

, (3.13)

,   (j = 4, 5).

Now multiply equation (3.13) by  and subtract from 2nd equation of system (3.12):

 (3.14)

 (j = 4, 5).

Then, when we have done this for all the pivots, we will be left with a reduced system of equations that looks like this:

 (3.15)

The procedure up to this point is termed Gaussian elimination.

But how do we solve for the xs? The last x (x4 in this example) is already isolated, namely

(3.16)

With the last x known we can move to the penultimate x,

(3.17)

and then proceed with the x before that one. The typical step is

(3.18)

The procedure defined by equation (3.18) is called backsubstitution. The combination of Gaussian elimination and backsubstitution yields a solution to the set of equations.

Example

Solve the following system of linear equations using Gaussian elimination and backsubstitution:

The pivot element is . Now divide the first equation by 2.0 to introduce 1 in the pivot position. We need to multiply the first equation by 0.4, 0.3 and 1.0 and subtract from 2nd, 3rd and 4th equations so those zeros are introduced in the first column everywhere except the first equation. The augmented matrix becomes:

.

The pivot element is . Hence we can use this element to introduce zeros in the 2nd column below 2nd row. Now divide the second row by 0.3 to introduce 1 in the pivot position. After that we multiply the second row by –1.15, and –0.3 and subtract from 3rd and 4th rows so those zeros are introduced in the second column everywhere except the first and second rows:

At the 3rd step the pivot element is . And after calculations the augmented matrix becomes:

Now divide the 4th row by 1.1199786 and begin backsubstitution:

6


 

А также другие работы, которые могут Вас заинтересовать

27064. Учет расчетов по недостачам 15.83 KB
  Учет расчетов по суммам выявленных недостач и хищений денежных средств и ценностей сумм потерь от порчи материальных ценностей и других сумм подлежащих удержанию и списанию в установленном порядке осуществляют на счете 020900000 Расчеты по недостачам . Учет расчетов по недостачам хищениям ведется в соответствии с КОСГУ на следующих счетах: 020971000 Расчеты по ущербу основным средствам ; 020972000 Расчеты по ущербу нематериальным активам ; 020973000 Расчеты по ущербу непроизведенным активам ; 020974000 Расчеты по ущербу материальных...
27065. Учет удержаний из заработной платы 16.39 KB
  Учет удержаний из заработной платы Счет 30403 Расчеты по удержаниям из выплат по оплате труда Счет предназначен для учета расчетов по удержаниям из заработной платы и денежного довольствия стипендий; безналичным перечислениям на счета во вклады сотрудников учреждения; взносам по договорам добровольного страхования; взносам на пенсионное страхование; суммам членских профсоюзных взносов; исполнительным листам и другим документам. Удержания производятся на основании соответствующих документов: письменных заявлений работников договоров...
27066. Учет расчетов с поставщиками и подрядчиками 12.95 KB
  Учет расчетов с поставщиками и подрядчиками Учет расчетов учреждения с поставщиками за поставленные материальные ценности и оказанные услуги с подрядчиками за выполненные работы осуществляют на счете 030200000 Расчеты с поставщиками и подрядчиками . Аналитический учет расчетов с поставщиками за поставленные материальные ценности оказанные услуги выполненные работы ведется в Карточке учета средств и расчетов либо в Журнале операций по расчетам с поставщиками и подрядчиками в разрезе кредиторов поставщиков продавцов подрядчиков...
27067. Учет бюджетных ассигнований и лимитов бюджетных обязательств 15.06 KB
  учет бюджетных ассигнований и лимитов бюджетных обязательств Счета предназначены для ведения учета учреждениями финансовыми органами показателей бюджетных ассигнований лимитов бюджетных обязательств сумм утвержденных сметой доходов и расходов по приносящей доход деятельности показателей по доходам поступлениям и расходам выплатам принятых учреждениями обязательств. По завершении текущего финансового года показатели остатки по счетам учета бюджетных ассигнований лимитов бюджетных обязательств текущего финансового года на следующий...
27068. Виды и формы бюджетной отчетности 16.13 KB
  Бюджетная отчетность предоставляется на бумажных носителях и или в виде электронного документа с представлением на электронных носителях или путем передачи по телекоммуникационным каналам связи в порядке установленном главным распорядителем бюджетных средств главным администратором доходов бюджета главным администратором источников финансирования дефицита бюджета финансовым органом органом казначейства и органом осуществляющим кассовое обслуживание с обязательным обеспечением защиты информации в соответствии с законодательством...
27069. Синтетический учет материальных запасов 16.14 KB
  Приобретение материальных запасов по фактической сформированной стоимости отражается по дебету соответствующих счетов аналитического учета счета 010500000 Материальные запасы 010531340 010536340 и кредиту счетов 030234730 Уменьшение кредиторской задолженности по приобретению материальных запасов 020834660 Уменьшение дебиторской задолженности подотчетных лиц по приобретению материальных запасов . Безвозмездное получение материальных запасов в том числе по централизованному снабжению распоряжению извещению отражается по дебету...
27070. Документальное оформление, порядок ведения и отражения в учете кассовых операций 16.09 KB
  Для учета кассовых операций применяются приходный кассовый ордер форма № КО1 расходный кассовый ордер форма КО2 журнал регистрации приходных и расходных кассовых документов форма КО3 кассовая книга форма КО4 книга учета принятых и выданных кассиром денежных средств форма КО5. Все операции по поступлению и расходованию денежных средств кассир записывает в кассовую книгу которая должна быть пронумерована прошнурована и опечатана сургучной печатью. В дебет его записывают поступление денежных средств в кассу а в кредит выбытие...
27071. Инвентаризация материальных запасов 15.97 KB
  Инвентаризация материальных запасов Методические указания по инвентаризации имущества и финансовых обязательств от 13 июня 1995 г . Инвентаризационной комиссией в описях заполняются данные о фактическом наличии товарноматериальных ценностей. Результаты проведенной инвентаризации материальных запасов отражают в инвентаризационной описи сличительной ведомости по объектам нефинансовых активов ф. При хранении материальных запасов в разных изолированных помещениях у одного материально ответственного лица инвентаризация проводится...
27072. Учет прочих доходов и расходов. Назначение счета «Прочие доходы и расходы» и его структура. Организация аналитического учета для формирования отчета «О прибылях и убытках» 23.5 KB
  Назначение счета Прочие доходы и расходы и его структура. Доходы и расходы организации формирующие финансовый результат ее деятельности В соответствии с Положением по бухгалтерскому учету Доходы организации ПБУ 9 99 введено в действие с 1 января 2000 г. Прочие поступления зачисляются на счет 91 Прочие доходы и расходы Прочими доходами признаются в учете: штрафы пени неустойки за нарушения условий договоров возмещения причиненных организации убытков в отчетном периоде в котором судом вынесено решение об их взыскании или они...