Qndev’s blog

Mô tả thiết kế phần mềm

2020-09-08T00:00:00+00:00

Tài liệu mô tả thiết kế phần mềm

---

Đặc tả yêu cầu phần mềm

2020-09-07T00:00:00+00:00

Tài liệu đặc tả yêu cầu phần mềm

---

Hệ điều hành

2020-07-01T00:00:00+00:00

Quản lý bộ nhớ, quản lý hệ thống file

---

Danh sách liên kết đơn dùng con trỏ

2019-12-21T00:00:00+00:00

Con trỏ cơ bản

#include<stdio.h>
 
int main() {
    int qndev = 50;
    int *p1;
    int **p2;
    p1 = &qndev;
    p2 = &p1;
    printf("Gia tri cua bien qndev: %d \n", qndev);
    printf("Dia chi cua bien qndev la: %x \n", &qndev);
    printf("Dia chi cua bien con tro p1 la: %x \n", &p1);
    printf("Gia tri cua bien con tro p1 la: %x \n", p1);
    printf("Gia tri cua bien ma con tro p1 tro toi la: %d \n", *p1);
    printf("Dia chi cua bien con tro p2 la: %x \n", &p2);
    printf("Gia tri cua bien con tro p2 la: %x \n", p2);
    printf("Gia tri cua bien ma con tro p2 tro toi la (Gia tri cua bien con tro p1/ Dia chi cua bien qndev): %x \n", *p2);
    printf("Gia tri cua bien **p2 la: %d \n", *(*p2));
    return 0;
}

Output:

Gia tri cua bien qndev: 50 
Dia chi cua bien qndev la: 33a8ea4c 
Dia chi cua bien con tro p1 la: 33a8ea40 
Gia tri cua bien con tro p1 la: 33a8ea4c 
Gia tri cua bien ma con tro p1 tro toi la: 50 
Dia chi cua bien con tro p2 la: 33a8ea38 
Gia tri cua bien con tro p2 la: 33a8ea40 
Gia tri cua bien ma con tro p2 tro toi la (Gia tri cua bien con tro p1/ Dia chi cua bien qndev): 33a8ea4c 
Gia tri cua bien **p2 la: 50 

Danh sách sách liên kết đơn

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
struct _PointerType{
  ElementType Inf;
  struct _PointerType *Next;
};
typedef struct _PointerType PointerType;

PointerType *BuildList() {
    PointerType *head = NULL;
    PointerType *second = NULL;
    PointerType *third = NULL;

    head = malloc(sizeof(PointerType));
    second = malloc(sizeof(PointerType));
    third = malloc(sizeof(PointerType));

    head->Inf = 2;
    head->Next = second;

    second->Inf = 3;
    second->Next = third;
    third->Inf = 4;
    third->Next = NULL;

    return head;
}

PointerType *InsertMiddle(PointerType *Prev, ElementType X)
{
  PointerType *TempNode;
  
  TempNode = (PointerType *)malloc(sizeof(PointerType));
  TempNode->Inf = X;
  TempNode->Next = Prev->Next;
  Prev->Next = TempNode;
  
  return TempNode;
}

ElementType Delete(PointerType *Prev){
  ElementType X;
  PointerType *TempNode;
  
  TempNode = Prev->Next; Prev->Next = Prev->Next->Next;
  X = TempNode->Inf;
  free(TempNode);
  
  return X;
}

PointerType *InsertToHead(PointerType *First, ElementType X){
  PointerType *TempNode;
  
  TempNode = (PointerType *) malloc(sizeof(PointerType));
  TempNode->Inf = X;
  TempNode->Next = First;
  First = TempNode;
  // printf("Gia tri cua First %p \n", First);
  return First;
}

PointerType *InsertToLast(PointerType *First, ElementType X){
  PointerType *NewNode; PointerType *TempNode;

  NewNode = (PointerType *)malloc(sizeof(PointerType));
  NewNode->Inf = X;NewNode->Next = NULL; 
  TempNode = First;
  
  while(TempNode->Next!=NULL)
    TempNode = TempNode->Next;
  
  TempNode->Next = NewNode;
  return First;
}

PointerType *DeleteHead(PointerType *First){
  PointerType *TempNode;
  
  TempNode = First->Next;
  free(First);
  
  return TempNode;
}

PointerType *DeleteLast(PointerType *First){
  PointerType *Temp1,*Temp2;
  Temp1 = First; Temp2 = First;
  
  while(Temp1->Next != NULL){
   Temp2 = Temp1;
   Temp1 = Temp1->Next;}
  
  Temp2->Next = NULL;
  free(Temp1);
  return First;
}

PointerType* Reverse(PointerType* head) { 
    
    if (head == NULL) 
        return NULL; 
    if (head->Next == NULL) { 
        return head;
    }

    PointerType* newHead = Reverse(head->Next);
    head->Next->Next = head;
    head->Next = NULL;

    return newHead;
}

int IsEmpty(PointerType *First)
{
  return !First;
}

PointerType *MakeNull(PointerType *First)
{
  while(!IsEmpty(First))
   First=DeleteHead(First);
  return First;
}

void Print(PointerType *First){
  PointerType *TempNode;
  
  printf("%p ",First);
  TempNode = First;
  while(TempNode!=NULL){
   printf("-> [ %d : %p ]",TempNode->Inf,TempNode->Next);
   TempNode = TempNode->Next;
  }
  printf("\n");
}

// Than chuong trinh chinh
int main(){
    PointerType *ds=NULL,*pv=NULL;
    int i,p;

    // Chen 5 gia tri vao vi tri dau
    ds = InsertToHead(ds,1);
    ds = InsertToHead(ds,2);
    ds = InsertToHead(ds,3);
    ds = InsertToHead(ds,4);
    ds = InsertToHead(ds,5);

    //PointerType *ds = BuildList();
    // In ra danh sach sau khi chen
    printf("In ra danh sach sau khi chen vao dau \n");
    Print(ds);
    
    printf("Danh sach sau khi chen 6 vao dau \n");
    ds = InsertToHead(ds,6);
    Print(ds);

    ds = Reverse(ds);
    printf("Danh sach sau khi dao nguoc \n");
    Print(ds);

    // Chen so 7 vao vi tri cuoi cua danh sach
    printf("Danh sach sau khi chen 7 vao cuoi \n");
    ds = InsertToLast(ds,7);
    Print(ds);
    
    // In ra danh sach sau khi xoa phan tu dau
    printf("In ra danh sach sau khi xoa dau \n");
    ds = DeleteHead(ds);
    Print(ds);
    
    // In ra danh sach sau khi xoa phan tu cuoi
    printf("In ra danh sach sau khi xoa cuoi \n");
    ds = DeleteLast(ds);
    Print(ds);
    
    // In ra danh sach sau khi xoa phan tu dau
    printf("Cho vi tri ban muon chen 7 vao sau p = ");scanf("%d",&p);
    pv = ds;i=1;
    while(i<p){pv = pv->Next;i++;}
    InsertMiddle(pv,7);
    Print(ds);
    getchar();
    return 0;
}

Output:

In ra danh sach sau khi chen vao dau 
0x55e09e4d92e0 -> [ 5 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d9280 ]-> [ 2 : 0x55e09e4d9260 ]-> [ 1 : (nil) ]
Danh sach sau khi chen 6 vao dau 
0x55e09e4d9710 -> [ 6 : 0x55e09e4d92e0 ]-> [ 5 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d9280 ]-> [ 2 : 0x55e09e4d9260 ]-> [ 1 : (nil) ]
Danh sach sau khi dao nguoc 
0x55e09e4d9260 -> [ 1 : 0x55e09e4d9280 ]-> [ 2 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92e0 ]-> [ 5 : 0x55e09e4d9710 ]-> [ 6 : (nil) ]
Danh sach sau khi chen 7 vao cuoi 
0x55e09e4d9260 -> [ 1 : 0x55e09e4d9280 ]-> [ 2 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92e0 ]-> [ 5 : 0x55e09e4d9710 ]-> [ 6 : 0x55e09e4d9730 ]-> [ 7 : (nil) ]
In ra danh sach sau khi xoa dau 
0x55e09e4d9280 -> [ 2 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92e0 ]-> [ 5 : 0x55e09e4d9710 ]-> [ 6 : 0x55e09e4d9730 ]-> [ 7 : (nil) ]
In ra danh sach sau khi xoa cuoi 
0x55e09e4d9280 -> [ 2 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92e0 ]-> [ 5 : 0x55e09e4d9710 ]-> [ 6 : (nil) ]
Cho vi tri ban muon chen 7 vao sau p = 5
0x55e09e4d9280 -> [ 2 : 0x55e09e4d92a0 ]-> [ 3 : 0x55e09e4d92c0 ]-> [ 4 : 0x55e09e4d92e0 ]-> [ 5 : 0x55e09e4d9710 ]-> [ 6 : 0x55e09e4d9730 ]-> [ 7 : (nil) ]

Transposes, permutations, spaces R^n [5]

2019-12-08T00:00:00+00:00

Permutations

Phép nhân với ma trận hoán vị \(P\) hoán đổi các hàng của ma trận; khi chúng ta thực hiện phương pháp khử, chúng ta sử dụng các ma trận hoán vị để chuyển các phần tử \(0\) ra khỏi vị trí chốt. Phép phân tích \(A=LU\) khi đó sẽ trở thành \(PA=LU\), với \(P\) là nma trận hoán vị sẽ sắp xếp lại bất kì hàng nào của ma trận \(A\). Và \(P^{-1}=P^T\), \(P^TP=I\).

Transposes

Khi chúng ta thực hiện chuyển vị ma trận, các hàng của chúng sẽ thành cột và các cột sẽ thành hàng. Nếu chúng ta kí hiệu phần tử ở hàng \(i\) cột \(j\) của ma trận \(A\) là \(A_{ij}\) thì chúng ta có thể biểu diễn \(A^T\) bằng: \(A_{ij}^T=A_{ji}\). Ví dụ:

\[ {\begin{bmatrix}1 & 3\\ 2 & 3\\ 4 & 1\end{bmatrix}}^T=\begin{bmatrix}1 & 2 & 4\\ 3 & 3 & 1\end{bmatrix} \]

Ma trận \(A\) là ma trận đối xứng nếu \(A^T=A\). Cho ma trận \(R\) bất kì không nhất thiết phải là ma trận vuông thì \(R^TR\) luôn luôn là ma trận đối xứng bởi vì \((R^TR)^T=R^T(R^T)^T=R^TR\). Chú ý: \((R^T)^T=R\).

Vector spaces

Chúng ta có thể công các vector, nhân vector với một số có nghĩa là chúng ta có thể thảo luận về tổ hợp tuyến tính của vectơ. Các tổ hợp tuyến tính này tuân theo các nguyên tắc của không gian vector.

Một không gian vectơ như vậy là \(\mathbb{R}^2\), tập hợp tất cả các vectơ với chính xác hai thành phần số thực. Chúng ta mô tả vector \(\begin{bmatrix}a \\ b\end{bmatrix}\) bằng cách vẽ mũi tên từ gốc tọa độ tới điểm có tọa độ \((a,b)\) đó là \(a\) đơn vị về phía bên phải và \(b\) đơn vị về phía trên, và chúng ta gọi \(\mathbb{R}^2\) là mặt phằng \(x-y\).

Một ví dụ khác về không gian đó là \(\mathbb{R}^n\), tập hợp các vectơ (cột) với n thành phần số thực.

Closure - tính bao đóng

Tập hợp các vectơ với chính xác hai thành phần có giá trị thực dương không phải là một không gian vectơ, bởi vì tổng của hai vectơ bất kì trong tập vẫn là vectơ thuộc tập đó nhưng nhân một số ví dụ \(-5\) với một vectơ thì kết quả lại không thuộc tập có hai thành phần giá trị thực dương ở trên.

Chúng ta nói tập hợp các vectơ dương này có tính bao đóng với phép cộng chứ không có tính bao đóng với phép nhân.

Nếu tập hợ các vectơ có tính bao đóng dưới tổ hợp tuyến tính (với cả phép cộng và phép nhân với bất kì số thực nào), và nếu phép nhân và phép cộng hoạt động theo cách này, thì chúng ta gọi tập hợp đó là không gian vectơ.

Subspaces - không gian vectơ con

Một không gian vectơ được chứa bên trong một không gian vectơ khác được gọi là không gian con của không gian đó. Ví dụ: lấy bất kì vectơ khác \(\vec 0\) bào trong \(\mathbb{R}^2\). Thì tập hợp các vectơ \(c\vec v\) (\(c\) là số thực), tạo thành một không gian con của \(\mathbb{R}^2\).Tập hợp các vectơ này mô tả một đường thẳng qua \(\begin{bmatrix}0 \\ 0\end{bmatrix}\) trong \(\mathbb{R}^2\) và được đóng kín đối với phép cộng.

Không gian vectơ con của \(\mathbb{R}^2\) là:

\(\mathbb{R}^2\)
\(\theta =(0,0)\)
đường thẳng qua \(\begin{bmatrix}0 \\ 0\end{bmatrix}\)

Không gian vectơ con của \(\mathbb{R}^3\) là:

\(\mathbb{R}^3\)
\(\theta =(0,0,0)\)
đường thẳng qua gốc tọa độ
mặt phẳng qua gốc tọa độ

Column space

Cho ma trận \(A\) với các cột thuộc \(\mathbb{R}^3\), các cột này và tổ hợp tuyến tính của chúng tạo thành một không gian vectơ con của \(\mathbb{R}^3\). Đây là không gian vectơ cột \(C(A)\). Nếu \(A=\begin{bmatrix}1 & 3 \\ 2 & 3 \\ 4 & 1\end{bmatrix}\), không gian vectơ cột của \(A\) là mặt phẳng đi qua gốc tọa độ của \(\mathbb{R}^3\) chứa \(\begin{bmatrix}1 \\ 2 \\ 4\end{bmatrix}\) và \(\begin{bmatrix}3 \\ 3 \\ 1\end{bmatrix}\).

MIT OpenCourseWare

18.06SC Linear Algebra / Fall 2011

Terms of Use

Factorization into A = LU [4]

2019-12-07T00:00:00+00:00

Inverse of a product - nghịc đảo của tích ma trận

Nghịch đảo của tích hai ma trận \(AB\) đó là \(B^{-1}A^{-1}\)

Transpose of a product - chuyển vị

Chúng ta có thể thu được chuyển vị của ma trận bằng cách hoán đổi các hàng và cột của nó. Hay nói theo cách khác đó là phần tử ở hàng \(i\) cột \(j\) của ma trận \(A\) sẽ là phần tử ở hàng \(j\) cột \(i\) của ma trận \(A^{T}\).

Chuyển vị của tích ma trận \(AB\) là \(B^{T}A^{T}\). Đối với bất kì ma trận khả nghịch \(A\), thì nghịc đảo của \(A^{T}\) là \((A^{-1})^T\):

\[ (A^{T})^{-1}=(A.A^{-1})^T.(A^T)^{-1}=(A^{-1})^T.(A^T).(A^T)^{-1}=(A^{-1})^T \]

A = LU

Chúng ta đã biết cách sử dụng phương pháp khử để chuyển đổi một ma trận \(A\) phù hợp thành một ma trận tam giác trên \(U\). Điều này dẫn đến phân tích thành nhân tử \(A\) thành \(LU\), điều mà rất hữu ích cho việc hiểu về ma trận \(A\).

Nhớ lại rằng chúng ta có thể mô tả phương pháp khử các phần tử của ma trận \(A\) (trong trường hợp không có việc hoán đổi các hàng trong khi thực hiện phép khử) theo cách nhân với một chuỗi các ma trận loại bỏ \(E_{ij}\), vì vậy \(A\to E_{21}A \to E_{31}E_{21} \to \cdots \to U\). Trong trường hợp ma trận kích thước \(2 \times 2\) như sau:

\[ E_{21}A=U \sim \begin{bmatrix}1 & 0 \\ -4 & 1\end{bmatrix}\begin{bmatrix}2 & 1 \\ 8 & 7\end{bmatrix}=\begin{bmatrix}2 & 1 \\ 0 & 3\end{bmatrix} \]

Chúng ta có thể chuyển đổi thành \(A=LU\) bằng cách loại bỏ ma trận \(E_{21}\); để làm đuược điều đó ta nhân hai vế của biểu thức với \(E_{21}A=U\) với ma trận nghịch đảo của nó \(E_{21}^{-1}\): \(E_{21}^{-1}E_{21}A=E_{21}^{-1}U\).

\[ A=LU\sim\begin{bmatrix}2 & 1 \\ 8 & 7\end{bmatrix}=\begin{bmatrix}1 & 0 \\ 4 & 1\end{bmatrix}\begin{bmatrix}2 & 1 \\ 0 & 3\end{bmatrix} \]

Ma trận \(U\) là ma trận tam giác trên với các phần tử chốt trên đường chéo. Ma trận \(L\) là ma trận tam giác dưới và cũng có các phần tử \(1\) trên đường chéo. Đôi khi chúng ta cũng sẽ muốn tạo ra một ma trận đường chéo mà các phần tử là phần tử chốt:

\[ A=LDU^{\mathbf’}\sim\begin{bmatrix}2 & 1 \\ 8 & 7\end{bmatrix}=\begin{bmatrix}1 & 0 \\ 4 & 1\end{bmatrix}\begin{bmatrix}2 & 0 \\ 0 & 3\end{bmatrix}\begin{bmatrix}1 & 1/2 \\ 0 & 1\end{bmatrix} \]

Trong trường hợp không gian ba chiều, nếu \(E_{32}E_{31}E_{21}A=U\) thì \(A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U=LU\).

Ví dụ, giả sử \(E_{31}\) là ma trận đơn vị và \(E_{32}\), \(E_{21}\) là hai ma trận dưới đây:

\[ E_{32}E_{21}=E \sim \begin{bmatrix}1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & -5 & 1\end{bmatrix}\begin{bmatrix}1 & 0 & 0\\ -2 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}=\begin{bmatrix}1 & 0 & 0\\ -2 & 1 & 0 \\ 10 & -5 & 1\end{bmatrix} \]

Phần tử \(10\) mới xuất hiện góc trái do ta trừ 2 lần dòng nhất từ dòng thứ hai, sau đó trừ 5 lần dòng mới thứ hai từ dòng thứ ba.

Phép phân tích thành nhân tử \(A=LU\) thích hợp hơn so với phép biến đổi \(EA=U\) bởi vì tổ hợp các phép trừ của các hàng không có tác động lên \(L\) như nó đã làm đối với \(E\). Và \(L=E^{-1}=E_{21}^{-1}E_{32}^{-1}\).

\[ E_{21}^{-1}E_{32}^{-1}=L \sim \begin{bmatrix}1 & 0 & 0\\ 2 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}\begin{bmatrix}1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 5 & 1\end{bmatrix}=\begin{bmatrix}1 & 0 & 0\\ 2 & 1 & 0 \\ 0 & 5 & 1\end{bmatrix} \]

Để ý rằng phần tử \(0\) ở hàng ba cột một của ma trận \(L=E^{-1}\), nơi mà có phần tử \(10\) của \(E\). Nếu không có sự tráo đổi hàng. các số nhân của ma trận loại bỏ được sao chép trực tiếp vào \(L\).

How expensive is elimination?

Một vài ứng dụng yêu cầu nghịch đảo các ma trận có kích thước rất lớn. Việc này thực hiện được là nhờ máy tính. Làm thế nào chúng ta có thể biết được máy tính làm viêc vất vả như thế nào? Chúng tốn bao nhiêu thời gian?

Có bao nhiêu phép tính mà máy tính thực thiện trong suốt quá trình thực thi phép khử đối với ma trận \(n\times n\)? Phép toán đặc trưng đó là phép nhân một hàng và sau đó trừ nó bởi hàng khác, đòi hỏi theo thứ tự của \(n\) phép tính. Có \(n\) hàng vì vậy tổng số phép toán sử dụng để khử các phần tử ở cột thứ nhất là \(n^2\). Dòng thứ hai và cột thứ hai thì có tổng số phép tính ít hơn với chi phí vào khoảng \(((n-1)^2\)) và tiếp tục với các hàng và cột khác của ma trận \(n\times n\). Như vậy tổng cộng chi phí hay số phép toán cần thực hiện để biến đổi \(A\) thành \(LU\) theo thứ tự là \(n^3\):

\[ 1^2+2^2+\cdots+(n-1)^2+n^2=\sum_{i=1}^n i^2\approx\displaystyle \int_0^nx^2dx=\frac{1}{3}n^3 \]

Trong khi chúng ta thực hiện phép biến đổi \(A\) đồng thời chúng ta cũng thực hiện trên \(\mathbf{b}\) với chi phí là \(n^2\) (chi phí này không đáng kể so với \(n^3\)).

Row exchanges

Điều gì sẽ xảy ra nếu cần phải hoán đổi các hàng với nhau trong khi thực hiện phép khử hay nói theo cách khác đó là điều gì sẽ xảy ra nếu có phần tử \(0\) ở vị trí chốt?

Để hoán đổi vị trí hai hàng với nhau ta nhân vào bên trái với ma trận hoán vị, ví dụ: Ma trận \(P_{12}=\begin{bmatrix}0 & 1 & 0\\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}\) hoán đổi hàng một và hai của ma trận \(3\times 3\). Nghịch đảo của ma trận \(P\) là \(P^{-1}=P^T\).

Có \(n!\) cách khác nhau để hoán đổi các hàng của ma trận \(n\times n\) vì vậy sẽ có \(n!\) ma trận hoán vị.

MIT OpenCourseWare

18.06SC Linear Algebra / Fall 2011

Terms of Use

Elimination with matrices [2]

2019-12-04T00:00:00+00:00

Method of Elimination

Phép khử là kỹ thuật được sử dụng bởi hầu hết các phần mềm máy tính để giải hệ phương trình tuyến tính. Nó tìm nghiệm \(\mathbf{x}\) của \(A\mathbf{x}=b\) khi ma trận \(A\) là ma trận nghịch đảo. Ví dụ:

\[A=\begin{bmatrix}\boxed 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1\end{bmatrix} and \; \mathbf{b}=\begin{bmatrix}2 \\ 12 \\ 2\end{bmatrix}\]

Số \(1\) mà ta đánh dấu trong ô vuông của ma trận \(A\) ở trên được gọi là phần tử chốt đầu tiên. Chúng ta lấy dòng đầu tiên rồi sau đó nhân từng phần tử của dòng với một số thích hợp (trong trường hợp này là \(3\)) rồi trừ đi các giá trị tương ứng của dòng thứ hai. Phần tử đầu tiên của dòng thứ hai sẽ bằng \(0\). Như vậy ta đã thực hiện phép khử phần tử \(3\) của dòng hai và cột một.

Bước tiếp theo ta thực hiện phép khử khác để biến phần tử ở hàng ba và cột một thành \(0\). Phần tử chốt thứ hai bây giờ xuất hiện tại vị trí hàng hai cột hai. Tiến hành tìm phần tử (trong trường hợp này là số \(2\)) để nhân với hàng hai để loại bỏ \(4\) ở hàng ba cột hai. Ta thu được phần tử chốt thứ ba là \(5\) ở vị trí hàng 3 cột 3 sau khi tiến hành lấy hàng ba trừ 2 nhân với hàng hai.

Như vậy chúng ta bắt đầu bằng ma trận khả nghịch \(A\) và biến nó thnahf ma trận tam giác trên \(U\), các phần tử bên trái phía dưới của \(U\) đều bằng \(0\) và các phần tử chốt \(1, 2, 5\) trên đường chéo của \(U\).

\[ A=\begin{bmatrix}\boxed 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1\end{bmatrix} \to \begin{bmatrix}\boxed 1 & 2 & 1 \\ 0 & \boxed 2 & -2 \\ 0 & 4 & 1\end{bmatrix} \to U=\begin{bmatrix}\boxed 1 & 2 & 1 \\ 0 & \boxed 2 & -2 \\ 0 & 0 & \boxed 5\end{bmatrix} \]

Chúng ta cũng thực hiện các phép khử tương ứng của ma trận \(A\) đối với vector \(\mathbf{b}=\begin{bmatrix}2 \\ 12 \\ 2\end{bmatrix}\).

Phép khử đã biến phương trình \(A\mathbf{x}=\mathbf{b}\) thành \(U\mathbf{x}=\mathbf{c}\), trong ví dụ trên \(U=\begin{bmatrix}1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5\end{bmatrix}\) được biến đổi từ \(A\) và \(\mathbf{c}=\begin{bmatrix}2 \\ 6 \\ -10\end{bmatrix}\) từ \(\mathbf{b}\).

Phương trình \(U\mathbf{x}=\mathbf{c}\) rõ ràng là dễ giải hơn bằng cách thay thế ngược các ẩn số từ dưới lên, trong ví dụ với phương trình này ta có thể viết thành hệ phương trình tuyến tính với 3 ẩn số \(\mathbf{x}=\begin{bmatrix}x \\ y \\ z\end{bmatrix}\):

\[ \left\{\begin{array}{rl} x + 2y + z & = 2 \
2y -2z & = 6 \
5z & = -10 \end{array}\right. \to z=-2, y=1, x=2 \]

Nghiệm \(\mathbf{x^T}=(2,1,-2)\) cũng là nghiệm của phương trình \(A\mathbf{x}=\mathbf{b}\).

Ta có định thức của \(U\) là tích của các phần tử chốt trên đường chéo. Các phần tử chốt này phải khác không, nếu có phần tử \(0\) tại vị trí chốt thì ta cần hoán đổi hàng đó với hàng không có phần tử \(0\) tại vị trí chốt. Nếu không có hàng nào thỏa mãn sau khi hoán đổi thì ma trận \(A\) không khả nghịch. Việc khử không được sử dụng để tìm một nghiệm duy nhất vì nó không tồn tại.

Elimination Matrices

Tích của ma trận (3x3) và vector cột (3x1) là một vector (3x1) đó là tổ hợp tuyến tính các cột của ma trận.

Tích của một hàng (1x3) và ma trận (3x3) là một hàng (1x3) là tổ hợp tuyến tính của các hàng của ma trận.

Việc phép khử để lấy phần tử chốt thứ hai bằng cách trừ 3 lần hàng một từ hàng hai (nghĩa là \(row(2)=-3.row(1)+row(2))\) tương đương với việc tính tích của hai ma trận dưới đây:

\[ \begin{bmatrix}1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}\begin{bmatrix}1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1\end{bmatrix}=\begin{bmatrix}1 & 2 & 1 \\ 0 & \boxed 2 & -2 \\ 0 & 4 & 1\end{bmatrix} \]

Ma trận khử được dùng để khử các phần tử ở hàng \(m\) cột \(n\) được kí hiệu là \(E_{mn}\). Việc tính toán trên đưa ma trận từ \(A\) thành \(E_{21}A\). Ba bước khử ở trên dẫn đến \(U\): \(E_{32}(E_{31}(E_{21}A))=U\) với \(E_{31}=I\), do đó:

\[E_{32}(E_{21}A)=U\]

Phép nhân ma trận có tính chất kết hợp vì vậy ta cũng có thể viết \((E_{32}E_{21})A=U\). Tích của hai ma trận \(E_{32}E_{21}\) cho chúng ta biết cách để biến đổi ma trận \(A\) thành ma trận \(U\). Nghịch đảo của ma trận \(E_{32}E_{21}\) cho chúng ta biết cách để biến đổi ma trận \(U\) thành ma trận \(A\).

\[{(E_{32}E_{21})}^{-1}(E_{32}E_{21})A={(E_{32}E_{21})}^{-1}U) \sim A={(E_{32}E_{21})}^{-1}U\]

Nếu chúng ta giải phương trình \(U\mathbf{x}=EA\mathbf{x}=E\mathbf{b}\), thì cũng đồng nghĩa với việc chúng ta giải phương trình \(A\mathbf{x}=\mathbf{b}\). Đây là lý do tại sao phương pháp khử hoạt động: tất cả các bước có thể được đảo ngược.

Một ma trận hoán vị trao đổi hai hàng của một ma trận; ví dụ:

\[ \begin{bmatrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix} \]

Hàng thứ nhất và hàng thứ hai của ma trận \(PA\) tương ứng là hàng thứ hai và hàng thứ nhất của ma trận \(A\). Ma trận \(P\) được xây dựng bằng cách trao đổi các hàng của ma trận đơn vị.

Để trao đổi các cột của ma trận ta thực hiện bằng cách nhân vào bên phải của ma trận đó (như trong \(AP\) với ma trận hoán vị. Lưu ý rằng phép nhân ma trận không có tính chất giao hoán: \(PA\ne AP\).

Inverses

Chúng ta có ma trận:

\[ E_{21}=\begin{bmatrix}1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix} \]

bằng cách \(row(2)-3.row(1)\), hay nói cách khác đó là phép biến đổi ma trận \(A\) ở ví dụ trên thành ma trận \(E_{21}A=\begin{bmatrix}1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1\end{bmatrix}\). Để hòa tác lại thao tác tính toán, biến đổi này hay biến ma trận \(E_{21}A\) trở lại ma trận \(A\) chúng ta cần sử dụng ma trận nghịc đảo:

\[ E_{21}^{-1}=\begin{bmatrix}1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix} \]

Và trong thực tế thì \(E_{21}^{-1}E_{21}=I\).

MIT OpenCourseWare

18.06SC Linear Algebra / Fall 2011

Terms of Use

Multiplication and inverse matrices [3]

2019-12-04T00:00:00+00:00

Matrix Multiplication - Phép nhân ma trận

Ta có tích của hai ma trận \(AB=C\), với \(A\) là ma trận \(m\)x\(n\), \(B\) là ma trận \(n\)x\(p\) thì \(C\) là ma trận \(m\)x\(p\). Chúng ta sẽ sử dụng \(c_{ij}\) để kí hiệu cho các giá trị ở hàng \(i\) và cột \(j\) của ma trận \(C\).

Standard (row times column) - hàng nhân cột

Cách cơ bản để miêu tả phép nhân ma trận đó là các giá trị \(c_{ij}\) bằng tích của hàng \(i\) của ma trận \(A\) và cột \(j\) của ma trận \(B\). Hay nói cách khác:

\[ c_{ij}=\sum_{k=1}^n a_{ik}b_{kj} \]

Columns - theo cột

Tích của ma trận \(A\) và cột \(j\) của ma trận \(B\) bằng cột \(j\) của ma trận \(C\). Điều này cho chúng ta biết rằng các cột của ma trận \(C\) là tổ hợp các cột của ma trận \(A\).

Rows - theo hàng

Tích của hàng \(i\) của ma trận \(A\) và ma trận \(B\) bằng hàng \(i\) của ma trận \(C\). Vì vậy các hàng của ma trận \(C\) là tổ hợp các hàng của ma trận \(B\).

Column times row - cột nhân hàng

Một cột của ma trận \(A\) là vector \(m\)x\(1\) và hàng của ma trận \(B\) là một vector \(1\)x\(p\). Tích của chúng là ma trận:

\[ \begin{bmatrix}2 \\ 3 \\ 4\end{bmatrix}\begin{bmatrix}1 & 6\end{bmatrix}=\begin{bmatrix}2 & 12 \\ 3 & 18 \\ 4 & 24\end{bmatrix} \]

Như vậy ta thấy các cột của ma trận \(\begin{bmatrix}2 & 12 \\ 3 & 18 \\ 4 & 24\end{bmatrix}\) là phép nhân của cột \(\begin{bmatrix}2 \\ 3 \\ 4\end{bmatrix}\)của ma trận \(A\) và các hàng của ma trận \(\begin{bmatrix}2 & 12 \\ 3 & 18 \\ 4 & 24\end{bmatrix}\) là phép nhân của hàng \(\begin{bmatrix}1 & 6\end{bmatrix}\) của ma trận \(B\).

Nếu chúng ta nghĩ về các giá trị, phần tử trong các hàng của ma trận này như những tọa độ điểm \((2,12)\), \((3,18)\), \((4,24)\), tất cả các điểm này cùng nằm trên một đường thẳng, tương tự như hai vector cột với hai điểm có tọa độ \((2,3,4)\) và \((12,18,24)\).

Như vậy \(AB=\sum_{k=1}^n \begin{bmatrix}a_{1k} \\ . \\ . \\ . \\ a_{mk}\end{bmatrix}\begin{bmatrix}b_{k1} & \ldots & b_{kn}\end{bmatrix}\).

Blocks - khối

Nếu chúng ta chia ma trận \(A\) và \(B\) ra thành các khối khớp nhau, chúng ta có thể viết tích \(AB\) dưới dạng của tích các khối:

\[ \begin{bmatrix}A_1 & A_2 \\ A_3 & A_4\end{bmatrix}\begin{bmatrix}B_1 & B_2 \\ B_3 & B_4\end{bmatrix}=\begin{bmatrix}C_1 & C_2 \\ C_3 & C_4\end{bmatrix} \]

Và \(C_1=A_1B_1+A_2B_3\).

Inverses - nghịch đảo ma trận

Square matrices - ma trận vuông

Nếu \(A\) là ma trận vuông, thì câu hỏi quan trọng nhất mà bạn có thể hỏi về nó là liệu \(A\) có ma trận nghich đảo \(A^{-1}\). Nếu câu trả lời là có, thì \(A^{-1}A=I=A^{-1}\) và chúng ta có thể nói rằng ma trận \(A\) là khả nghịch hay không suy biến.

Nếu ma trận \(A\) là ma trận suy biến. Ma trận \(A\) không có ma trận nghịc đảo - định thức của nó bằng \(0\) và chúng ta có thể tìm thấy một vài vector \(\mathbf{x}\) để \(A\mathbf{x}=0\). Ví dụ:

\[ \begin{bmatrix}1 & 3 \\ 2 & 6\end{bmatrix}\begin{bmatrix}3 \\ -1\end{bmatrix}=\begin{bmatrix}0 \\ 0\end{bmatrix} \]

Trong ví dụ này \(3.\begin{bmatrix}1 \\ 2\end{bmatrix}-1.\begin{bmatrix}3 \\ 6\end{bmatrix}=\begin{bmatrix}0 \\ 0\end{bmatrix}\) và cả hai vector cột trong ma trận đó đều nằm trên một đường thẳng.

Việc tìm kiếm ma trận nghịch đảo gần như liên quan đến việc giải hệ phương trình tuyến tính:

\[ \begin{bmatrix}1 & 3 \\ 2 & 7\end{bmatrix}\begin{bmatrix}a & c \\ b & d\end{bmatrix}=\begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}\sim AA^{-1}=I \]

có thể đọc như việc nói “\(A\) nhân với cột \(j\) của ma trận \(A^{-1}\) bằng cột \(j\) của ma trận đơn vị”. Đay chỉ là một dạng đặc biệt của phương trình \(A\mathbf{x}=\mathbf{b}\).

Gauss-Jordan Elimination - phương pháp khử Gauss

Chúng ta có thể sử dụng phương pháp khử để giải hai hay nhiều phương trình tuyến tính tại cùng một thời điểm.

Ta chỉ cần đặt song song hai ma trận \(A\) và ma trận đơn vị \(I\) sau đó dùng hệ thống các phép biến đổi không suy biến đồng thời trên các hàng của \(A\) và \(I\) (thực chất của mỗi phép biến đổi chính là nhân cả \(A\) và \(I\) với cùng một ma trận không suy biến). Sau một số hữu hạn bước biến \(A\) thành \(I\) - thực chất là đưa ra ma trận \(E\) để \(EA=I\) còn ma trận \(I\) thì trở thành ma trận \(EI=E=A^{-1}\) \((E \times \Big[ \ A \; \Big| \; I \ \Big] = \Big[ \ EA \; \Big| \; EI \ \Big] = \Big[ \ I \; \Big| \; E \ \Big])\).

\[ \Big[ \ A \; \Big| \; I \ \Big] \to \Big[ \ I \; \Big| \; A^{-1} \ \Big] \]

\[ \left[ \begin{array}{cc|cc} 1 & 3 & 1 & 0 \
2 & 7 & 0 & 1 \
\end{array} \right] \to \left[ \begin{array}{cc|cc} 1 & 3 & 1 & 0 \
0 & 1 & -2 & 1 \
\end{array} \right] \to \left[ \begin{array}{cc|cc} 1 & 0 & 7 & -3 \
0 & 1 & -2 & 1 \
\end{array} \right] \]

Một lần nữa chúng ta đã sử dụng phương pháp khử Gauss để biến ma trận ban đầu thành ma trận tam giác trên, và tiếp tục sử dụng ý tưởng của Jordan về việc khử các phần tử ở phía trên bên phải của ma trận.

\[ A^{-1}=\begin{bmatrix}7 & -3 \\ -2 & 1\end{bmatrix} \]

MIT OpenCourseWare

18.06SC Linear Algebra / Fall 2011

Terms of Use

The Geometry of Linear Equations [1]

2019-12-03T00:00:00+00:00

The geometry of linear equations - Ý nghĩa hình học của phương trình tuyến tính

Vấn đề cơ bản của đại số tuyến tính là giải hệ phương trình tuyến tính với \(n\) ẩn số; ví dụ: \[ \left\{\begin{matrix} 2x - y = 0\
-x + 2y = 3 \end{matrix}\right. \]

Chúng ta sẽ tìm hiểu vấn đề này theo 3 cách. Hệ bên trên là hệ phương trình tuyến tính tring không gian vector hai chiều \((n=2)\).

Row Picture

Nghiệm của hệ phương trình tuyến tính trên chính là giao điểm của hai đường thẳng đại diện cho hai phương trình trong hệ đó. Nhìn vào bức ảnh dưới đay ta có thể thấy \(x=1\), \(y=2\) là nghiệm của hệ phương trình.

Để kiểm chứng lại nghiệm đó ta thây \((x,y)=(1,2)\) vào hệ:

\[ \left\{\begin{matrix} 2.1 - 2 = 0\
-1 + 2.2 = 3 \end{matrix}\right. \]

Nghiệm của hệ phương trình tuyến tính trong không gian ba chiều là giao điểm của ba mặt phẳng(nếu hệ có nghiệm).

Column Picture

Chúng ta sẽ xem hệ phương trình tuyến tính giống như một phương trình bằng cách biến các hệ số thành các vector:

\[ x\begin{bmatrix} 2 \
-1 \end{bmatrix}+y\begin{bmatrix} -1 \
2 \end{bmatrix}=\begin{bmatrix} 0 \
3 \end{bmatrix} \]

Cho hai vectors \(c\) và \(d\) và các số vô hướng \(x\) và \(y\), tổng \(xc+yd\) được gọi là tổ hợp tuyến tính của \(c\) và \(d\).

Với \(x=1\) và \(y=2\) thì tổ hợp tuyến tính của hai vector \(\begin{bmatrix}2 \\ -1\end{bmatrix}\) và \(\begin{bmatrix}1 \\ -2\end{bmatrix}\) sẽ bằng vector \(\\(\begin{bmatrix}0 \\ 3\end{bmatrix}\)) được biểu diễn bằng hình ảnh dưới đây:

Trong không gian vector ba chiều column picture yêu cầu chúng ta phải tìm kiếm một tổ hợp tuyến tính của các vector 3 chiều sao cho chúng bằng vector \(b\).

Matrix Picture

Chúng ta sẽ viết hệ phương trình tuyến tính \(\left\{\begin{matrix}2x - y = 0 \\ -x + 2y = 3\end{matrix}\right.\) thành một phương trình bằng cách sử dụng ma trận và vector:

\[ \begin{bmatrix}2 & -1\\ -1 & 2\end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix}=\begin{bmatrix}0 \\ 3\end{bmatrix} \]

Ma trận \(A=\begin{bmatrix}2 & -1\\ -1 & 2\end{bmatrix}\) được gọi là ma trận hệ số. Vector \(x=\begin{bmatrix}x \\ y\end{bmatrix}\) là vector của ẩn số. Các giá trị phía bên tay phải của phương trình là vector \(b\) \[Ax=b.\]

Không gian ba chiều của matrix picture cũng giống như hai chiều ngoại trừ việc kích cỡ của vector và matrix được tăng lên.

Matrix Multiplication

Làm sao chúng ta có thể nhân một ma trận \(A\) với một vector \(x\)?

\[ \begin{bmatrix}2 & 5\\ 1 & 3\end{bmatrix}\begin{bmatrix}1 \\ 2\end{bmatrix}=\;? \]

Một cách mà ta có thể nghĩ tới đó là phần tử của \(x\) giống như các hệ số của một tổ hợp tuyến tính của các vector cột của ma trận:

\[ \begin{bmatrix}2 & 5\\ 1 & 3\end{bmatrix}\begin{bmatrix}1 \\ 2\end{bmatrix}=1\begin{bmatrix}1 \\ 2\end{bmatrix}+2\begin{bmatrix}5 \\ 3\end{bmatrix}=\begin{bmatrix}12 \\ 7\end{bmatrix} \]

Kỹ thuật này sẽ biểu diễn \(Ax\) là một tổ hợp tuyến tính các cột của \(A\). Bạn cũng có thể thực hiện việc tính toán phép nhân \(Ax\) bằng cách nhân từng hàng của ma trận \(A\) với vector \(x\):

\[ \begin{bmatrix}2 & 5\\ 1 & 3\end{bmatrix}\begin{bmatrix}1 \\ 2\end{bmatrix}=\begin{bmatrix}2.1 + 5.2\\ 1.1 + 3.2\end{bmatrix}=\begin{bmatrix}12 \\ 7\end{bmatrix} \]

Linear Independence

Trong cột và bức tranh về ma trận, bên phải của phương trình là vector \(b\). Cho ma trận \(A\), chúng ta có thể giải được phương trình: \[Ax=b\] với mọi vector \(b\)? Hay nói cách khác là tổ hượp tuyến tính của các vector cột có thể bao phủ hết mặt phẳng tọa độ \(xy\) (hoặc không gian trong trường hợp không gian ba chiều)? Nếu câu trả lời là không, chúng ta gọi \(A\) là ma trận suy biến. Trong trường hợp này các vector cột của nó là phụ thuộc tuyến tính; tất cả các tổ hợp tuyến tính nằm trên một điểm, đường thẳng (trong không gian hai chiều) hoặc trên một điểm, đường thẳng, mặt phẳng (trong không gian ba chiều). Các tổ hợp không bao phủ, lấp đầy toàn bộ không gian.

MIT OpenCourseWare

18.06SC Linear Algebra / Fall 2011

Terms of Use

Phương trình tuyến tính trong đại số tuyến tính - Notes

2019-11-30T00:00:00+00:00

Hệ phương trình tuyến tính

Một phương trình tuyến tính với các biến \(x_1,x_2,x_3,…,x_n\) trong phưowng trình có thể viết dưới dạng: \[a_1x_1 + a_2x_2 + … + a_nx_n = b \tag{1}\] trong đó \(b\) và các hệ số \(a_1,a_2,…,a_n\) là các số thực. Các chỉ số \(n\) là các số nguyên dương. Ví dụ: Các phương trình: \[-x_1 + 15x_1 + 4x_2 = 1996 \; và \; x_2 = 28x_1 +2x_3 + 15\] là các phương trình tuyến tính bởi khi ta rút gọn chúng lạ ta có \(14x_1 + 4x_2 = 1996 \; và \; 28x_1 - x_2 +2x_3 = -15 \)có dạng (1). Các phương trình: \(4x_1 - 5x_2 = x_1x_2 \; và \; x_2 = 2\sqrt{x_1} -6\) không phải là các phương trình tuyến tính.

Hệ phương trình tuyến tính hay hệ tuyến tính là tổ hợp của một hoặc nhiều phương trình tuyến tính có liên quan đến các biến giống nhau được gọi là \(x_1,x_2,…,x_n \). Ví dụ: Ta có hệ phương trình: \[\begin{cases} 2x_1 - x_2 + 1.5x_3 = 8 \\ x_1 + 0x_2 - 4x_3 = -7 \end{cases} \tag{2}\]

Lời giải của hệ là danh sách \((s_1,s_2,s_3,…,s_n)\) các số mà tại đó làm thoả mãn từng phương trình trong hệ (các giá trị \(s_1,s_2,s_3,…,s_n\)) thay thế tương ứng chó các biến (\(x_1,x_2,x_3,…,x_n\)). Ví dụ: \((5,6.5,3)\) là lời giải cho hệ phương trình (2) bởi vì khi thay thế các số thực trên tương ứng với \(x_1,x_2,x_3\) của hệ ta được các phương trình luôn đúng: \(8 = 8 \; và -7 = -7\).

Tất cả các lời giải có thể thoả mãn hệ được gọi là tập lời giải (tập nghiệm). Hai hệ phương trình tuyến tính được gọi là tương đương nhau nếu chúng có cùng tập nghiệm.

Chú ý: Một hệ phương trình tuyến tính có thể có: không có nghiệm hoặc có chính xác một nghiệm duy nhất hoặc có vô số nghiệm.

Ví dụ: Ta có hệ phương trình: \(\begin{cases} x_1 - 2x_2 = -1 \\ -x_1 + 3x_2 = 3 \; \end{cases}\) có nghiệm duy nhất.

Trong hệ trên hệ pt có cặp nghiệm \((x_1,x_2) = (3,2)\).

Hệ phương trình: \(\begin{cases} x_1 - 2x_2 = -1 \\ -x_1 + 2x_2 = 3 \; \end{cases}\) không có nghiệm.

Hệ phương trình: \(\begin{cases} x_1 - 2x_2 = -1 \\ -x_1 + 2x_2 = 1 \; \end{cases}\) có vô số nghiệm.

Một hệ phương trình được gọi là thoả mãn nếu chúng hoặc có một nghiệm hoặc vô số nghiệm, hệ pt không thoả mãn nếu chúng vô nghiệm.

Kí hiệu ma trận

Các thông tin cần thiết của một hệ phương trình tuyến tính có thể ghi lại gọn trong một hình chữ nhật bao gồm các hệ số của hệ phương trình được gọi là ma trận. Ta có hệ pt sau: \[ \left\{ \begin{array}{ll} x_1 - 2x_2 + x_3 &= 0 \
2x_2 - 8x_3 &= 8 \
5x_1 -5x_3 &= 10 \end{array} \right. \tag{3}\]

Với các hệ số tương ứng với các biến của các cột như sau: \(\begin{bmatrix}1 & -2 & 1 \\ 0 & 2 & -8 \\ 5 & 0 & -5 \end{bmatrix}\) ma trận các hệ số của hệ pt (3).

Và ma trận \(\begin{bmatrix}1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 5 & 0 & -5 & 10 \end{bmatrix}\) (4) được gọi là ma trận bổ sung của hệ.

Chú ý: Ở hàng 2 và hàng 3 của các ma trận trên có các phần tử 0 tương ứng với các hệ số tương ứng với các biến \(x_1\) và \(x_2\) của phương trình (2) và (3) của hệ (3) nhưng không được xuất hiện. Cụ thể ta có thể viết lại pt (2) và (3) của hệ (3) như sau: \(0x_1+2x_2-8x_3 = 8\) và \(5x_1+0x_2-5x_3 = 10\). Ma trận bổ sung bên trên có thêm cột bên phải là các hằng số bên phải của các phương trình trong hệ.

Kích thước của ma trận được thể hiện thông qua các chỉ số hàng và cột mà ma trận có. Ma trận (4) có 3 hàng và 4 cột được gọi là ma trận 3 nhân 4 (3 by 4).

Giải hệ phương trình tuyến tính

Giải hệ phương trình tuyến tính (3)

Lời giải: Thực hiện thủ tục khử (loại bỏ) được biểu hiện bằng hệ phương trình và ma trận hệ số của hệ phương trình song song để dễ dàng so sánh.

\[ \left\{ \begin{array}{ll} x_1 - 2x_2 + x_3 &= 0 \
2x_2 - 8x_3 &= 8 \
5x_1 - 5x_3 &= 10 \end{array} \right. \; \; \; \; \; \begin{bmatrix}1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 5 & 0 & -5 & 10 \end{bmatrix}\]

Giữ nguyên \(x_1\) của phương trình đầu tiên cà thực hiện phương pháp khử (loại bỏ) nó từ các phương trình khác trong hệ. Để làm được điều đó ta tiến hành cộng \((-5)\) với phương trình (1) với phương trình (3).

\[\begin{align}-5.[pt1] \\ + [pt2] \\ [pt3 \; mới]\end{align}\; \; \; \; \; \left\{ \begin{array}{ll} 5x_1 + 10x_2 - 5x_3 &= 0 \
5x_1 - 5x_3 &= 10 \
10x_2 - 10x_3 &= 10 \end{array} \right.\]

Kết quả của việc tính toán trên được viết thay thế pt3 của hệ.

\[ \left\{ \begin{array}{ll} x_1 - 2x_2 + x_3 &= 0 \
2x_2 - 8x_3 &= 8 \
10x_2 - 10x_3 &= 10 \end{array} \right. \; \; \; \; \; \begin{bmatrix}1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & 10 & -10 & 10 \end{bmatrix}\]

Bây giờ nhân phương trình (2) của hệ với \(1\over2\) theo thứ tự ta thu được hệ số của \(x_2\) là 1.

\[ \left\{ \begin{array}{ll} x_1 - 2x_2 + x_3 &= 0 \
x_2 - 4x_3 &= 4 \
10x_2 - 10x_3 &= 10 \end{array} \right. \; \; \; \; \; \begin{bmatrix}1 & -2 & 1 & 0 \\ 0 & 1 & -4 & 4 \\ 0 & 10 & -10 & 10 \end{bmatrix}\]

Sử dụng \(x_2\) của phương trình (2) để khử \(10x_2\) của phương trình (3).

\[\begin{align}-10.[pt2] \\ + [pt3] \\ [pt3 \; mới]\end{align}\; \; \; \; \; \begin{cases} -10x_2 + 40x_3 &= -40 \
10x_2 - 10x_3 &= 10 \
30x_3 &= -30 \end{cases} \]

Kết quả của việc tính toán trên ta thu được phương trình thứ 3 mới của hệ.

\[ \left\{ \begin{array}{ll} x_1 - 2x_2 + x_3 &= 0 \
x_2 - 4x_3 &= 4 \
30x_3 &= -30 \end{array} \right. \; \; \; \; \; \begin{bmatrix}1 & -2 & 1 & 0 \\ 0 & 1 & -4 & 4 \\ 0 & 0 & 30 & -30 \end{bmatrix}\]

Bây giờ tiếp tục nhân phương trình (3) với \(1\over30\) ta thu được hệ số 1 của \(x_3\).

\[ \left\{ \begin{array}{ll} x_1 - 2x_2 + x_3 &= 0 \
x_2 - 4x_3 &= 4 \
x_3 &= -1 \end{array} \right. \; \; \; \; \; \begin{bmatrix}1 & -2 & 1 & 0 \\ 0 & 1 & -4 & 4 \\ 0 & 0 & 1 & -1 \end{bmatrix}\]

Hệ phương trình tuyến tính mới ta thu được có dạng tam giác.

Cuối cùng, loại bỏ \(-2x_2\) của phương trình (1), nhưng để hiệu quả hơn ta sử dụng \(x_3\) của phương trình (3) trước, ta tiến hành loại bỏ \(-4x_3\) và \(+x_3\) của phương trình (2) và (1). Dưới đây là miêu tả việc tính toán đó:

\( \begin{align}4.[pt3] \\ + [pt2] \\ [pt2 \; mới]\end{align} \begin{cases} 4x_3 &= -4 \
x_2 - 4x_3 &= 4 \
x_2 &= 0 \end{cases} \) \(\;\;\;\) \( \begin{align}-1.[pt3] \\ + [pt1] \\ [pt1 \; mới]\end{align} \begin{cases} -x_3 &= 1 \
x_1 - 2x_2 + x_3 &= 0 \
x_1 - 2x_2 &= 1 \end{cases} \)

Kết quả ta thu được:

\[ \left\{ \begin{array}{ll} x_1 - 2x_2 &= 1 \
x_2 &= 0 \
x_3 &= -1 \end{array} \right. \; \; \; \; \; \begin{bmatrix}1 & -2 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 \end{bmatrix}\]

Ta đã tìm được \(x_3\) ở phương trình (3) và sử dụng \(x_2\) của phương trình (2) để khử \(-2x_2\) của phương trình (1) bằng cách cộng 2 lần phương trình (2) với phương trình (1) ta thu được:

\[ \left\{ \begin{array}{ll} x_1 &= 1 \
x_2 &= 0 \
x_3 &= -1 \end{array} \right. \; \; \; \; \; \begin{bmatrix}1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 \end{bmatrix}\]

Như vậy hệ phương trình đã cho có nghiệm duy nhất và có rất nhiều cách khác nhau để tính toán, loại bỏ các hệ số trong hệ có thể dùng để tìm nghiệm của hệ. Để kiểm tra lại xem nghiệm tìm được có chính xác không ta thế các giá trị \((x_1,x_2,x_3)\) vừa tìm được vào bên trái của hệ xem kết quả có đúng bằng phía bên phải là các giá trị trong cột bổ sung của ma trận hay không.

\[\begin{align}1 - 2(0) + 1(-1) &= 0\\ 2(0) -8(-1) &= 8\\ 5(1) - 5(-1) &= 10\end{align}\]

Thao tác khử các hệ số của các phương trình trong hệ (phép khử): Thay thế phương trình(hàng) bằng tổng của chính nó với bội số của hàng khác; hoán đổi hai phương trình (hai hàng); nhân giá trị của phương trình với một hằng số khác không.

Vector Equations

Vector trong \(\mathbb{R}^2\)

Một ma trận chỉ có một cột được gọi là vector cột hay thường gọi là vector. Ví dụ: một vector với hai phần tử

\[\vec u = \begin{bmatrix}3 \\ -1\end{bmatrix}, \vec v = \begin{bmatrix}0.2 \\ 0.3\end{bmatrix}, \vec w = \begin{bmatrix}w_1 \\ w_2\end{bmatrix}\]

Với vector \(w\), \(w_1\) và \(w_2\) là các số thực. Tập hopwj tất cả các vector với hai phần tử được kí hiệu là: \(\mathbb{R}^2\). \(\mathbb{R}\) được kí hiệu như là đại diện cho một phần tử số thực trong vector và số 2 trên thể hiện việc vector có hai phần tử số thực. Hai vector được gọi là bằng nhau nếu phần tử tương ứng của chúng bằng nhau. Vector \(\begin{bmatrix}4 \\ 7\end{bmatrix}\) và \(\begin{bmatrix}7 \\ 4\end{bmatrix}\) là không bằng nhau.

Tổng của hai vector \(\vec u\) và \(\vec v\) thuộc \(\mathbb{R}^2\) thu được bằng cách cộng các phần tử tương ứng của \(\vec u\) và \(\vec v\). Ví dụ:

\[ \begin{bmatrix}1 \\ -2\end{bmatrix} + \begin{bmatrix}2 \\ 5\end{bmatrix} = \begin{bmatrix}1+2 \\ -2+5\end{bmatrix} = \begin{bmatrix}3 \\ 3\end{bmatrix} \]

Nhân số vô hướng \(c\) với một vector bằng cách nhân tương ứng từng phần tử của vector với số vô hướng \(c\) đó. Ví dụ:

\[ \vec u = \begin{bmatrix}3 \\ -5\end{bmatrix} and \; c = 5, cu = 5\begin{bmatrix}3 \\ -5\end{bmatrix} = \begin{bmatrix}15 \\ -25\end{bmatrix} \] số thực \(c\) trong \(cu\) được gọi là scalar giá trị vô hướng.

Biểu diễn trong hình học \(\mathbb{R}^2\)

Tọa độ điểm	Vectors theo mũi tên

Quy tắc hình bình hành trong việc công vector.

Nếu vectors \(u\) và \(v\) thuộc \(\mathbb{R}^2\) được thể hiện giống như các điểm trong mặt phẳng thì \(u+v\) tương ứng là đỉnh thứ tư của hình bình hành tạo cùng với ba đỉnh còn lại là \(u\), \(0\) và \(v\). Hình ảnh minh họa dưới đây cho thấy rõ điều đấy:

Ở đây các vector \(u = \begin{bmatrix}2 \\ 3\end{bmatrix}\) - vector màu xanh, \(v = \begin{bmatrix}-1 \\ 1\end{bmatrix}\) - vector màu đỏ, \(0 = \begin{bmatrix}0 \\ 0\end{bmatrix}\) - gốc tọa độ và vector \(u+v = \begin{bmatrix}1 \\ 4\end{bmatrix}\) - vector màu vàng.

Vector thuộc \(\mathbb{R}^3\)

Vector thuộc \(\mathbb{R}^3\) là ma trận 3x1 với 3 phần tử. Biểu diễn tương ứng trong hình học là điểm trong hệ tọa độ không gian ba chiều.

Vector thuộc \(\mathbb{R}^n\)

Nếu \(n\) là số nguyên dương, \(\mathbb{R}^n\) là kí hiệu của tập hợp danh sách của \(n\) số thực, thường được viết giống như ma trận cột nx1.

\[ \vec u = \begin{bmatrix}u_1 \\ u_2 \\ . \\ . \\u_n\end{bmatrix} \]

Vector mà tất cả các phần tử của nó bằng 0 được gọi là vector không.

Tổ hợp tuyến tính

Các vetor \(\vec v_1,\vec v_2,…,\vec v_p\) thuộc \(\mathbb{R}^n\) và các số vô hướng \(c_1,c_2,…,c_p\). Vector \(\vec y\) được định nghĩa dưới dạng: \(\vec y = c_1\vec v_1 + c_2\vec v_2 + … + c_p\vec v_p\) được gọi là tổ hợp tuyến tính của \(\vec v_1,\vec v_2,…,\vec v_p\) với các trọng số \(c_1,c_2,…,c_p\). Các trọng số trong tổ hợp tuyến tính có thể là bất kì số thực nào kể cả là 0. Ví dụ: Một vài tổ hợp tuyến tính của hai vector \(\vec v_1, \vec v_2\).

\[ \sqrt{3}\vec v_1 + \vec v_2, \frac{1}{2}\vec v_1 + 0\vec v_2, 0\vec v_1 + 0\vec v_2 \]

\(\mathbf{Ax=b}\)

\[\mathbf{Ax} = \begin{bmatrix}a_1 & a_2 & . & . & a_n\end{bmatrix}\begin{bmatrix}x_1 \\ x_2 \\ . \\ . \\ x_n\end{bmatrix} = a_1x_1 + a_2x_2 + … + a_nx_n\]

\[\mathbf{Ax=b} \sim a_1x_1 + a_2x_2 + … + a_nx_n = b \sim \begin{bmatrix}a_1 & a_2 & . & . & a_n & b\end{bmatrix}\]

Tập nghiệm của hệ phương trình tuyến tính

Hệ thuần nhất có dạng \(\mathbf{Ax=0}\) có nghiệm không tầm thường khi và chỉ khi phương trình có ít nhất một biến tự do(là biến với hệ số bằng không).

Ví dụ: \(\begin{bmatrix}A & 0\end{bmatrix}\)

\[ \begin{bmatrix}3 & 5 & -4 & 0 \\ -3 & -2 & 4 & 0 \\ 6 & 1 & -8 & 0\end{bmatrix} \sim \begin{bmatrix}3 & 5 & -4 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & -9 & 0 & 0\end{bmatrix} \sim \begin{bmatrix}3 & 5 & -4 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0\end{bmatrix} \]

\[ \begin{bmatrix}1 & 0 & \frac{-4}{3} & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0\end{bmatrix} \; \; \; \begin{cases} x_1 - \frac{4}{3}x_3 &= 0 \
x_2 &= 0 \
0 &= 0 \end{cases} \]

Như vậy ta có \(x_1 = \frac{4}{3}x_3\), \(x_2 = 0\), suy ra \(\mathbf{x} = \begin{bmatrix}x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix}\frac{4}{3}x_3 \\ 0 \\ x_3 \end{bmatrix} =vx_3\) với \(v=\begin{bmatrix}\frac{4}{3} \\ 0 \\ 1\end{bmatrix}\)

Ta có \(vx_3 = \begin{bmatrix}\frac{4}{3} \\ 0 \\ 1\end{bmatrix}\). Về mặt hình học, tập nghiệm của hệ phương trình là đường thẳng đi qua gốc tọa độ trong \(\mathbb{R}^3\).

Ví dụ: \(10x_1-3x_2-2x_3=0\), suy ra \(x_1=0.3x_2+0.2x_3\).

\[ \mathbf{x} = \begin{bmatrix}x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix}0.3x_2+0.2x_3 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix}0.3x_2 \\ x_2 \\ 0 \end{bmatrix} + \begin{bmatrix}0.2x_3 \\ 0 \\ x_3 \end{bmatrix}
\]

\[ \mathbf{x} = x_2\begin{bmatrix}0.3 \\ 1 \\ 0 \end{bmatrix} + x_3\begin{bmatrix}0.2 \\ 0 \\ 1 \end{bmatrix} \]

Như vậy tập nghiệm của pt là tổ hợp tuyến tính của hai vector \(u\) và \(v\) với \(u=\begin{bmatrix}0.3 \\ 1 \\ 0 \end{bmatrix}\) và \(v=\begin{bmatrix}0.2 \\ 0 \\ 1 \end{bmatrix}\) hay \(span{u,v}\) hay mặt phẳng đi qua gốc tọa độ chứa \(u\) và \(v\).

Tập nghiệm dạng: \(\mathbf{x}=su+tv\) \((s,t\in\mathbb{R})\).

Nghiệm của hệ không thuần nhất

\(w=p+v_h\) trong đó \(v_h\) là nghiệm của \(\mathbf{Ax=0}\).

Độc lập tuyến tính

Tập \(\{v_1,v_2,\ldots,v_p\}\in\mathbb{R}\) được gọi là độc lập tuyến tính nếu pt:

\[ x_1v_1+x_2v_2+\cdots+x_pv_p=0 \]

chỉ có nghiệm tầm thường và phụ thuộc tuyến tính nếu tồn tại các trọng số \(c_1,c_2,\ldots,c_p\) không đồng thời bằng \(0\)

\[ c_1v_1+c_2v_2+\cdots+c_pv_p=0 \]