Phép nhân ma trận

Thông thường, để đạt được độ phức tạp lý tưởng của thuật toán, cách để đạt được nó thường là tìm một thuật toán ban đầu làm cơ sở, sau đó sử dụng các thủ thuật để giảm độ phức tạp của thuật toán. Trong bài viết này, tôi xin giới thiệu một kỹ năng tương đối phổ biến: Phép nhân ma trận.

Xác định

Ma trận là một mảng hình chữ nhật gồm các số, ký hiệu hoặc biểu thức, được sắp xếp theo hàng và cột, mỗi hàng tuân theo các quy tắc được xác định trước. Các ô trong ma trận được gọi là các phần tử của ma trận. Các phần tử được xác định bởi 2 địa chỉ ở hàng i và cột j (ký hiệu là aij

Xem thêm: Nhân ma trận với ma trận

).

Ma trận thường được viết trong ngoặc vuông:

Kích thước hay kích thước của một ma trận được xác định bởi số lượng hàng và cột. Một ma trận có m hàng và n cột được gọi là ma trận (m×n), và m và n

Gọi là buổi chiều.

• Ví dụ:Ma trận a

là ma trận (3×2)

Hình vuông

Ma trận vuông là ma trận có số hàng và số cột bằng nhau. Ma trận (n×n) còn được gọi là ma trận vuông cấp n. tất cả các phần tử

Tạo thành đường chéo chính của ma trận vuông.

• Ví dụ:Ma trận vuông bậc 3

(Số hàng và số cột đều bằng 3)

Ma trận nhận dạng

Ma trận đơn vị cấp n là ma trận (n×n) trong đó mỗi phần tử trên đường chéo chính bằng 1 và các phần tử khác bằng 0. Ma trận đơn vị cấp n cũng là ma trận vuông cấp n

.Ví dụ

Vectơ hàng và vectơ cột

vectơ hàng hoặc ma ​​trận hàng là ma trận (1×n), tức là ma trận chỉ có một hàng n

phần tử

.

a=[a1 a2 … an]

Vectơ cột hoặc Ma trận cột là một ma trận (m×1), nghĩa là một ma trận chỉ bao gồm một cột gồm m phần tử.

Phép nhân ma trận

Hai ma trận chỉ có thể được nhân với nhau nếu số cột trong ma trận thứ nhất phải bằng số hàng trong ma trận thứ hai. Ma trận kết quả được gọi là tích ma trận và có số hàng của ma trận thứ nhất và số cột của ma trận thứ hai.

Nếu kích thước của ma trận a là (m×n) và kích thước của ma trận b là (n×p), thì kích thước của ma trận sản phẩm c=a×b là (m×p) và kích thước của hàng thứ i và cột thứ j Các thành phần được xác định theo công thức:

Tính chất của phép nhân ma trận

• Thuộc tính liên kết: (ab)c=a(bc)

. Thuộc tính phân phối: (a+b)c=ac+bc và c(a+b)=ca+cb. Phép nhân ma trận không có tính chất giao hoán: tích ab có thể xác định được, nhưng 3 không nhất thiết phải xác định, tức là nếu a và b có kích thước lần lượt là (m×n) và (n×p) và m≠p .Ngay cả khi hai tích này tồn tại, chúng không nhất thiết phải bằng nhau, nghĩa là ab≠ba.

• Ví dụ:

Khi nhân một ma trận bất kỳ với ma ​​trận căn thì vẫn thu được kết quả là ma trận đó, cụ thể là: ain=ima=a (với ma trận a cỡ a) cỡ bất kỳ (m×n)). Cũng đúng Vì thuộc tính này, i được gọi là ma ​​trận đơn vị.

Sức mạnh ma trận

Cho ma trận vuông cấp n a. Sau đó, chúng ta có một ma trận được tính theo lũy thừa của k (ký hiệu: ak), trong đó k là một số nguyên không âm.

Do tính kết hợp của phép nhân ma trận, chúng ta có thể sử dụng phương pháp chia để trị để tính nhanh lũy thừa của ma trận, tương tự như phép tính hàm mũ thông thường. /strong> (Tính ak, trong đó a là số nguyên).

Cài đặt

Lưu ý: Khác với định nghĩa trên, trong cách thực hiện dưới đây, các hàng và cột của ma trận được đánh số từ 0 để thuận tiện cho việc xử lý.

Nhận xét

Ngoài cách cài đặt bật nguồn ở trên, chúng ta còn có thể cài đặt theo cách đệ quy như sau:

Độ phức tạp

Ví dụ 1

Hãy xem ví dụ kinh điển nhất về ứng dụng của phép nhân ma trận.

Toán học

Đối với hình chữ nhật 2×n (1≤n≤109). Đếm số cách đặt của các viên gạch nhỏ 1×2 và 2×1 trong hình trên và đảm bảo rằng một phần của các viên gạch nhỏ không bị sót lại bên ngoài và khu vực hình chữ nhật không được lát kém. .

Phân tích

fi là số cách xếp những viên gạch nhỏ thành hình chữ nhật 2×i

.Ta có:

• Nếu sử dụng gạch 1×2

Vậy thì fi=fi−2. Nếu sử dụng gạch 2×1 thì fi=fi−1

• .

⇒fi=fi−1+fi−2.

Rõ ràng phương pháp phổ biến là tính toán fis một cách tuần tự. Tuy nhiên, điều này hoàn toàn không hoạt động cho n đến 109

Chúng ta cần một cách tiếp cận khác.

Chúng tôi xem xét lớp số:

Chúng tôi tưởng tượng mỗi lớp là một ma trận (2×1). Tiếp theo, chúng ta sẽ chuyển từ lớp i−1 sang lớp i. Sau mỗi lần biến đổi như vậy ta được thêm một giá trị fi. Để thực hiện phép biến đổi này, các bạn chú ý các số ở lớp tiếp theo chỉ phụ thuộc vào phép cộng của lớp trước nó, chúng ta có thể tìm cách thực hiện phép biến đổi thông qua phép nhân ma trận:

Vậy bài toán trên rút gọn về dạng nhân ma trận. fn được tính từ lũy thừa của ma trận a

.Cài đặt

Lưu ý: Khác với định nghĩa ở trên. Trong cách thực hiện dưới đây, các hàng và cột của ma trận được đánh số bắt đầu từ 0

Để dễ xử lý.

Nhận xét

Độ phức tạp

Độ phức tạp của thuật toán là o(t×23×logn). trong đó t là số lượng bộ kiểm tra.

Ví dụ 2

Bây giờ, hãy xem một ví dụ tổng quát hơn về Ví dụ 1.

Toán học

Đang xem: Cách xem giờ theo 12 con giáp hoàng đạo chuẩn và mới nhất

Cài đặt

Lưu ý: Khác với định nghĩa ở trên. Trong cách thực hiện dưới đây, các hàng và cột của ma trận được đánh số bắt đầu từ 0 để tiện cho việc xử lý.

Nhận xét

Độ phức tạp

Độ phức tạp của thuật toán là o(t×k3×log(n−k)). trong đó t là số lượng bộ kiểm tra.

Ví dụ 3

Toán học

Một loại vi khuẩn mới vừa được phát hiện. Chúng sống thành n nhóm (n≤100), được đánh số từ 0 đến n-1. Ban đầu, mỗi khuẩn lạc này chỉ chứa một loại vi khuẩn. Tuy nhiên, cứ mỗi giây, số lượng vi khuẩn trong một thuộc địa lại thay đổi: một số vi khuẩn có thể chết, nhân lên hoặc di chuyển đến một thuộc địa khác. Những thay đổi này luôn tuân theo những quy luật đã có từ trước. Chỉ có một quy tắc xuất hiện mỗi giây. Các quy tắc này được thực hiện tuần tự và theo chu kỳ. Nghĩa là, nếu các quy tắc được đánh số từ 0 đến m−1, thì quy tắc được áp dụng tại giây thứ s sẽ là (s−1)modm (m≤1000)

. Nhiệm vụ của bạn là tìm xem có bao nhiêu vi khuẩn trong mỗi thuộc địa sau t đơn vị thời gian (t≤1018) với một bộ quy tắc.

Các loại quy tắc có thể có:

Phân tích

Cách dễ nhất là chúng tôi mô phỏng số lượng vi khuẩn trên mỗi thuộc địa trên mỗi đơn vị thời gian. Độ phức tạp của phương pháp này là o(t×n×k), trong đó o(k) là độ phức tạp đối với các số lớn. Cách này không hoạt động với t

Lớn.

Chúng tôi tưởng tượng số lượng vi khuẩn trên mỗi thuộc địa trong một đơn vị thời gian là một chuỗi số. Do đó, mỗi quy tắc đưa ra thực chất là một phép chuyển đổi một dãy số thành một dãy số mới và chúng ta có thể hoàn thành phép chuyển đổi này thông qua phép nhân ma trận.

Cụ thể hơn, chúng tôi coi số lượng vi khuẩn trong n khuẩn lạc tại một thời điểm nhất định là ma trận 1×n và mỗi lần biến đổi là ma trận n×n

.Khi áp dụng mỗi phép biến đổi ta nhân hai ma trận trên.

Bây giờ xét trường hợp n=4, ma trận tương ứng với phép biến đổi được mô tả như sau:

• Chuyển đổi: a 2 0

• Chuyển đổi: b 2 6

• Chuyển đổi: c 1 3

• Chuyển đổi: d 1 3

• Chuyển đổi: e 1 3

• Chuyển đổi: f 0 0

  Như trong bài toán trước, chúng ta sẽ thử áp dụng phép lũy thừa, kết hợp với phép nhân ma trận, để giảm độ phức tạp từ t xuống logt

  .Tuy nhiên, có thể thấy việc sử dụng lũy ​​thừa trong bài toán này phức tạp hơn một chút do các ma trận không trùng nhau. Để giải quyết vấn đề này, chúng tôi đã làm như sau:

  gọi x1,x2,…,xm

  là ma trận tương ứng với phép biến đổi đã cho.

  Cho x=x1×x2×…×xm

  .

  Đặt s=[1,1,…,1]

  (số lượng vi khuẩn đầu tiên)

  Vì vậy, y=s×xt×x1×x2×…×xr là ma trận biểu thị số lượng vi khuẩn tại thời điểm m×t+r

  .

  Vì vậy, thuật toán ở đây rất rõ ràng. Chúng tôi phân tích t=m×t+r, vì vậy chúng tôi có thể giải quyết vấn đề trong các bước ma trận O(n3×m) x và các bước tính toán O(n3×(logt/m+m)) y. Vấn đề đã được giải quyết.

  Ví dụ 4

  Toán học

  số đẹp là số nguyên dương, nếu số lẻ (1,3,5,7,9) xuất hiện số lần lẻ thì số chẵn (0,2,4,6,8) cũng xuất hiện số chẵn lần nếu nó xảy ra. Ví dụ số 141222124 là số đẹp. Gọi fn là số các số đẹp có không quá n chữ số. Tìm số n (1≤n≤1018) để tính fnmod1000000123.

  Phân tích

  Cách dễ nhất là sử dụng lập trình động với 4 trạng thái:

  Chúng tôi không phải lưu số lần xuất hiện của một số chẵn, bởi vì nếu số chẵn không xảy ra, nó sẽ được tính nếu số lần xuất hiện là số chẵn. p>

  Do đó, ta có công thức quy hoạch động sau:

  Bạn có thể tìm hiểu thêm về kỹ thuật lập trình động sử dụng đệ quy từ trên xuống tại đây.

  Vì số lượng số lẻ xuất hiện trong thời gian lẻ không thể vượt quá số lượng số lẻ đã xuất hiện nên chúng tôi có thể tối ưu hóa số lượng trạng thái thành khoảng 6×6×6 / 2. Khi đó, độ phức tạp của thuật toán trên sẽ là o(n×(6×6×6 / 2))

  .Tuy nhiên, n≤1018

  Khi đó hiển nhiên thuật toán trên sẽ lỗi thời cả về thời gian và bộ nhớ.

  Vì vậy, chúng ta cần cải tiến thuật toán bằng cách lũy thừa ma trận, sao cho số trạng thái của lớp dp là 6×6×6 / 2=108

  .Tối ưu hóa thuật toán, chia n thành lũy thừa 2 rồi sử dụng ma trận hệ số tương ứng đã tính sẵn để tính nhanh kết quả.

  Đang xem: Cách xem giờ theo 12 con giáp hoàng đạo chuẩn và mới nhất

  Cài đặt

  Lưu ý: Trong cách triển khai dưới đây, các hàng và cột của ma trận được đánh số từ 0 để dễ xử lý.

  Nhận xét

  Độ phức tạp

  Chúng ta mất độ phức tạp o(6×6×6 / 2)

  Dùng để xây dựng ma trận hệ số.

  Do kích thước của ma trận kết quả là ((số trạng thái)×1) thay vì ((số trạng thái)×(số trạng thái) nên độ phức tạp nhân ma trận của kết quả tính toán là (số trạng thái) 2 thay vì (số trạng thái) 3. Vậy độ phức tạp của thuật toán là o(log1018×1082)

  .

  Ngoài ra, ngay cả khi chúng tôi không giảm số lượng trạng thái xuống còn khoảng 6×6×6 / 2

  Vậy thì thuật toán này vẫn có thể thực hiện được.

  Ví dụ 5

  Toán học

  Phân tích

  Bằng quy nạp, ta dễ dàng chứng minh được 2

  Định lý sau:

  • Định luật 1: Cho dãy f1=a,f2=b,…,fn=fn−1+fn−2 (n>2)

  Khi đó fn=b×fn−1+a×fn−2 (n>2), trong đó fi là phần tử thứ i của dãy Fibonacci

  • Định luật 2: Cho dãy f1=a,f2=b,…,fn=fn−1+fn−2 (n>2)

  Sau đó f1+f2+…+fn=fn+2−b.

  a cũng có các thuộc tính của dãy Fibonacci

  Như sau:

  • Chúng ta có thể chuyển đổi hai số hạng đầu tiên của dãy Fibonacci
  • Nhận phạm vi mới.
  • gọi f1

  , f2 là hai dãy mới được hình thành sau khi chuyển đổi hai số hạng đầu tiên của dãy Fibonacci, và dãy f3 được định nghĩa là f3 i=f1 i+f2 i (i≥1) thì dãy f3 vẫn tiếp tục công thức đệ quy fn=fn−1+fn−2.

  Sau khi sử dụng các thuộc tính trên, bài toán trở thành một phép toán rất cơ bản của cây đoạn thẳng (it tree – cây khoảng / cây đoạn). Lưu trữ hai giá trị đầu tiên của chuỗi cho mỗi nút của cây phân đoạn.

  Trong bài viết này, tôi sẽ sử dụng phương pháp nhân ma trận kết hợp với cây phân đoạn để giải bài toán này. Đối với mỗi nút của cây, hãy lưu ma trận hệ số của dãy Fibonacci

  .Cài đặt

  Lưu ý: Trong cách triển khai bên dưới, các hàng và cột của ma trận được đánh số từ 0

  Để dễ xử lý.

  Nhận xét

  Trong thuật toán này, chúng ta sử dụng mảng tĩnh để lưu trữ ma trận thay vì mảng động (vectơ) như trong câu hỏi trước. Vì số lượng ma trận được lưu nhiều nhất là 4×n

  Vì vậy, việc khai báo một mảng động sẽ khiến thuật toán hết thời gian chờ.

  Độ phức tạp

  Đối với mỗi truy vấn, chúng tôi mất độ phức tạp o(logn)

  Được sử dụng cho các thao tác trên cây phân đoạn. Và chúng ta cũng mất o(22) và o(23) khi cộng và nhân ma trận. Nói chung, độ phức tạp của thuật toán là o(m×logn×23).

  Ví dụ 6

  Phép nhân ma trận tổng tối thiểu

  Tôi thấy rằng chúng ta hoàn toàn có thể thay thế phép nhân và phép cộng trong định nghĩa của phép nhân ma trận, nhưng chúng ta phải duy trì tính kết hợp. Cụ thể hơn, trong đó a và b là hai ma trận vuông cấp n

  ta có thể định nghĩa phép “nhân ma trận” mới như sau:

  Nó còn được gọi là Phép nhân ma trận cộng tối thiểu hoặc Tích ma trận khoảng cách.

  Từ đó, chúng ta có thể suy ra một dạng vấn đề khác. Ví dụ sau minh họa bộ câu hỏi này.

  Toán học

  Cho đồ thị có hướng có trọng số gồm n đỉnh và m cạnh. Tìm đường đi ngắn nhất từ ​​đỉnh 1 đến đỉnh n đi qua đúng k

  Cạnh.

  • n≤100
  • 1≤m≤n(n−1)
  • 1≤k≤109

  Phân tích

  Gọi ma trận c(k) kích thước n x n, trong đó c(k)[i,j] là độ dài của đường đi ngắn nhất từ ​​i đến j đi qua chính xác k cạnh.

  Hãy coi ma trận a là ma trận kề của đồ thị đã cho. Chúng tôi có:

  c(1)=a

  • c(2)[i,j]=min(a[i,u]+a[u,j])

  1≤u≤n

  • c(k)[i,j]=min(c(k−1)[i,u]+a[u,j])

  1≤u≤n

  Vì vậy, nếu chúng ta thay phép nhân và phép cộng trong phép nhân ma trận thông thường bằng phép cộng và min tương ứng, chúng ta sẽ nhận được một “phép nhân ma trận” mới, ký hiệu là ⋆, khi đó:

  c(1)=a

  c(2)=c(1)⋆c(1)=a⋆c(1)

  c(3)=c(1)⋆c(2)=a⋆c(2)

  c(4)=c(1)⋆c(3)=a⋆c(3)

  …

  c(k)=c(1)⋆c(k−1)=a⋆c(k−1)

  Do đó, c(k)=ak

  Vậy bài toán quay trở lại bài toán tính lũy thừa của ma trận, ta có thể giải chính xác như ví dụ trước. Việc thực hiện phép nhân ma trận mới này không phức tạp hơn việc thực hiện phép nhân ma trận thông thường. Phần cài đặt dành cho người đọc.

  Mối liên kết và độ phức tạp tính toán

  Mảng ma trận nhân

  Trong phần cài đặt, chúng ta đã có sẵn thuật toán nhân hai ma trận a

  kích thước (m×n) và kích thước b (n×p) yêu cầu độ phức tạp o(m×n×p). Giả sử chúng ta có thêm một ma trận c kích thước (p×q) và chúng ta cần tính tích a×b×c. Hãy xem xét hai cách để thực hiện phép nhân này:

  Phương pháp 1: (a×b)×c nhân với a và b rồi nhân với c yêu cầu độ phức tạp o(m×n×p)+o(m×p×q )= o (m×p×(n+q))

  Phương pháp 2: a×(b×c) nhân với b và c rồi nhân với a yêu cầu độ phức tạp o(n×p×q)+o(m×n×q) ) =o (n×q×(m+p)).

  Vì vậy, hai cách triển khai khác nhau đòi hỏi hai mức độ phức tạp khác nhau. Ví dụ:

  • Với m=n=500,p=1000,q=2

  .Phương thức 1 yêu cầu 500×1000×(500+2)=251×106 thao tác, trong khi phương thức 2 chỉ yêu cầu 500×2×(500+1000)=1,5×106 thao tác, nghĩa là phương pháp 1 hiệu quả hơn hơn Phương pháp 1 là chậm. 2 đến gần 200 lần.

  Sự khác biệt trở nên lớn hơn khi độ dài chuỗi ma trận tăng lên. Các ví dụ trên cho thấy rằng trong một số trường hợp, thứ tự của phép nhân ma trận là rất quan trọng trong việc tìm ra lời giải cho một bài toán.

  Kiểm tra thuật toán freivalds cho tích của hai ma trận

  Thuật toán freivalds là một ví dụ điển hình, áp dụng thứ tự thực hiện phép nhân ma trận để giảm độ phức tạp tính toán của phép nhân ma trận. Bài toán là ba ma trận vuông a, b, c cỡ n×n và n≤1000. Ta cần kiểm tra xem c có phải là tích của a và b hay không hay nói cách khác là ta cần kiểm tra xem a×b=c có đúng không (đây là bài vmatrix – vnoi marathon 2014).

  Phân tích

  Cách thông thường là nhân trực tiếp hai ma trận a và b

  Sau đó so sánh kết quả với c. Như đã đánh giá trong phần thiết lập, độ phức tạp của phương pháp này là O(n3), không đủ nhanh cho n=1000. Thuật toán freivalds được kiểm tra bằng thuật toán xác suất kiểu Monte Carlo, với k phép thử, xác suất đưa ra kết luận sai là khoảng 2−k và độ phức tạp của mỗi phép thử là O(n2). Các bước cơ bản của phép thử freivalds như sau:

  Tạo ngẫu nhiên một ma trận v có kích thước (n×1), trong đó các phần tử chỉ có thể là 0 hoặc 1

  • Ý nghĩa p=a×b×v−c×v

  .Dễ thấy p là ma trận cấp n×1

  • Trả về true nếu p chỉ chứa 0 phần tử (bằng vector 0), ngược lại trả về false.

  Chúng tôi thực hiện k lần thử và nếu chúng tôi gặp một phép thử trả về giá trị sai, chúng tôi kết luận rằng a×b≠c. Ngược lại, nếu sau k phép thử ta luôn thấy đúng thì ta kết luận rằng a × b = c. Vì xác suất sai giảm theo cấp số nhân với k, nên thường chỉ cần chọn đủ k để có xác suất đúng rất cao (k=5, vmatrix ở trên). Một nhận xét quan trọng khác là giới hạn trên của ước lượng xác suất kiểm tra lỗi không phụ thuộc vào kích thước n của ma trận đã cho, mà chỉ phụ thuộc vào số lần thực hiện kiểm tra.

  Xem xét bước thứ hai, chúng ta thấy rằng phép thử freivalds chỉ có ý nghĩa nếu chúng ta có thể thực hiện phép nhân a×b×v trong thời gian o(n2) (vì phép nhân c×v đã được thực hiện rồi o)(n2) ) .Thay vì làm theo thứ tự từ trái sang phải yêu cầu o(n3) thì ta làm theo thứ tự a×(b×v). Vì kết quả của phép nhân b và v là một ma trận (n×1), nên tổng độ phức tạp sẽ là o(n2). Trong tất cả các thí nghiệm, độ phức tạp là o(k×n2).

  Phép nhân ma trận

  Trong đại số tuyến tính, ma trận đóng một vai trò quan trọng trong việc xử lý các khái niệm khác nhau. Ma trận là một mảng hoặc bảng hình chữ nhật gồm các số, ký hiệu hoặc biểu thức, được sắp xếp theo hàng và cột trong toán học. Chúng ta có thể thực hiện các phép toán khác nhau trên ma trận như cộng, trừ, nhân, v.v. Trong bài học này, bạn sẽ học cách nhân một ma trận với một ma trận khác, thuật toán, công thức, phép nhân ma trận 2 × 2 và 3 × 3 cùng các ví dụ chi tiết.

  Định nghĩa phép nhân ma trận

  Phép nhân ma trận, còn được gọi là phép nhân ma trận và phép nhân hai ma trận, tạo ra một ma trận duy nhất. Đây là một hoạt động nhị phân.

  Nếu a và b là hai ma trận thì tích của hai ma trận a và b được biểu diễn như sau:

  x = ab

  Như vậy, tích của hai ma trận là tích vô hướng của hai ma trận.

  Ma trận lần vô hướng

  Phép nhân số nguyên với ma trận chỉ là phép nhân vô hướng.

  Chúng ta biết rằng ma trận là một dãy số. Nó bao gồm các hàng và cột. Nếu bạn nhân một ma trận với một giá trị vô hướng, nó được gọi là phép nhân vô hướng. Một trường hợp khác là một ma trận có thể được nhân với một ma trận khác. Hãy xem một ví dụ dưới đây.

  Chúng ta có thể định nghĩa một cách toán học phép nhân ma trận vô hướng là:

  Nếu a = [a ij ] m × n là một ma trận và k là một đại lượng vô hướng, thì ka là một ma trận khác thu được bằng cách nhân từng phần tử của a với k đại lượng vô hướng.

  Nói cách khác, ka = k [a ij ] m × n = [k (a ij )] m × n, tức là phần tử thứ (i, j) của ka là ka ij với mọi giá trị có thể có của tôi và j.

  Ví dụ: Nhân ma trận = [3049-15] với 4.

  Giải pháp thay thế:

  Được rồi,

  a = [3049-15]

  4 × a = 4 × [3049-15]

  Bây giờ chúng ta phải nhân từng phần tử của ma trận a với 4.

  = [1201636-420]

  Đây là ma trận mong muốn sau khi nhân ma trận đã cho với một giá trị không đổi hoặc vô hướng (tức là 4).

  Điều kiện nhân ma trận

  Để thực hiện phép nhân hai ma trận, ta phải đảm bảo số cột của ma trận thứ nhất bằng số hàng của ma trận thứ hai. Do đó, tích của các ma trận kết quả sẽ có nhiều hàng như ma trận thứ nhất và nhiều cột như ma trận thứ hai. Thứ tự của ma trận kết quả là thứ tự của phép nhân ma trận.

  Bây giờ, hãy xem cách thực hiện phép nhân ma trận cho các ma trận có thứ tự hoặc loại khác nhau.

  Làm thế nào để ma trận nhân lên?

  Hãy học cách nhân các ma trận.

  Hãy coi ma trận a là a × b và ma trận b là ab × c.

  Khi đó, ma trận c = ab được định nghĩa là ma trận a × b.

  Tham khảo: Hướng dẫn, thủ thuật về iPhone – iOS

  Một phần tử trong ma trận c, c xy được định nghĩa là c xy = a x1 b y1 +… .. + a xb b by = ∑bk = 1 a xk b ky for x = 1 …. . .a và y = 1…….c

  Đây là một trong những chủ đề quan trọng nhất ở lớp 12. 12 Loại Bài toán Ma trận giải quyết chi tiết các loại ma trận.

  Biểu tượng

  Nếu a là ma trận am×n, b là ma trận ap×q thì tích ma trận của a và b được biểu diễn như sau:

  x = ab

  Trong đó x là ma trận kết quả có kích thước m x ​​q.

  Công thức nhân ma trận

  Hãy lấy một ví dụ để hiểu công thức này.

  Giả sử a và b là hai ma trận nên

  a =⎡⎣⎢⎢⎢a11a21am 1a12a22………………….am 2⋯⋯⋯a1 na2ma n⎤⎦⎥⎥⎥,b=⎡⎣⎢⎢⎢b11b21bm 1b12b22…………….bm 2⋯⋯⋯b1 nb2 nbm n⎤⎦⎥⎥⎥Ma trận c = ab được biểu diễn dưới dạng

  c = ⎡⎣⎢⎢⎢c11c12…….c1 cc21c22…….c2 c………………… hình nón 1 hình nón 2………… hình nón

  Một phần tử trong ma trận c, trong đó c là tích của ma trận ax b.

  c = c xy = a x1 b y1 +… .. + a xb b by = ∑bk = 1 a xk b ky với x = 1 …… a và y = 1 … ….c

  Thuật toán nhân ma trận

  Trong những năm gần đây, đã có rất nhiều công trình nghiên cứu về thuật toán nhân ma trận do những ứng dụng của nó trong nhiều lĩnh vực. Có bốn loại thuật toán:

  • Thuật toán lặp
  • Thuật toán chia để trị
  • Thuật toán khối con
  • Thuật toán song song và phân tán

  Điều này chủ yếu được sử dụng trong các ngôn ngữ lập trình khác nhau như c và java để nhân trực tuyến. Phổ biến nhất là phép nhân ma trận 2 × 2, 3 × 3 và 4 × 4.

  Toán học là hệ nhị phân, với một tập hợp các mục nhập xác định cho các phép toán cộng, trừ, nhân và chia. Các phép toán này giống như đối với số thực và số hữu tỉ.

  Mặc dù ma trận có nhiều ứng dụng nhưng phép nhân ma trận về cơ bản là một phép toán trong đại số tuyến tính. Các ánh xạ tuyến tính, bao gồm phép cộng và phép nhân vô hướng, được biểu diễn bằng phép nhân ma trận.

  Người ta cũng có thể tìm thấy nhiều thuật toán khác nhau trên lưới. Loại thuật toán này được thiết kế để giảm bớt sự kém hiệu quả cố hữu của thuật toán mảng tiêu chuẩn, vốn có thể gặp phải độ trễ khi dữ liệu đến từ 2 ma trận khác nhau.

  Quy tắc nhân ma trận

  Theo công thức và quy trình được xác định ở trên, chúng ta có thể viết các quy tắc và tính chất sau của phép nhân ma trận.

  • Xác định tích của hai ma trận a và b nếu số cột của a bằng số hàng của b.
  • Nếu đã xác định ab thì không cần xác định ba
  • Nếu a và b là cùng một ma trận vuông thì ab và ba đều xác định.
  • Ab = ba không bắt buộc nếu cả ab và ba đều được xác định.
  • Nếu tích của hai ma trận là ma trận 0, thì một trong hai ma trận không nhất thiết phải là ma trận 0.

  Nhân ma trận 2 × 2

  Xét phép nhân ma trận 2 × 2 đơn giản a = [3479] và một ma trận khác b = [652 số 8]

  Bây giờ mỗi phần tử của ma trận tích ab có thể được tính như sau:

  • ab 11 = 3 × 6 + 7 × 5 = 53
  • ab 12 = 3 x 2 + 7 x 8 = 62
  • ab 21 = 4 × 6 + 9 × 5 = 69
  • ab 22 = 4 x 2 + 9 x 8 = 80

  Vậy ma trận ab = [53696280]

  Nhân ma trận 3×3

  Để hiểu phép nhân hai ma trận 3 × 3, ta xét hai ma trận 3 × 3 a và b.

  Ma trận a = ⎡⎣⎢1239số 817số 841410⎤⎦⎥, ma trận b = ⎡⎣⎢5671915số 83916⎤⎦⎥

  Mỗi phần tử của ma trận tích ab có thể được tính như sau:

  • ab 11 = 12 × 5 + 8 × 6 + 4 × 7 = 136
  • ab 12 = 12 x 19 + 8 x 15 + 4 x 8 = 380
  • ab 13 = 12 x 3 + 8 x 9 + 4 x 16 = 172
  • ab 21 = 3 × 5 + 17 × 6 + 14 × 7 = 215
  • ab 22 = 3 x 19 + 17 x 15 + 14 x 8 = 424
  • ab 23 = 3 x 3 + 17 x 9 + 14 x 16 = 386
  • ab 31 = 9 x 5 + 8 x 6 + 10 x 7 = 163
  • ab 32 = 9 x 19 + 8 x 15 + 10 x 8 = 371
  • ab 33 = 9 x 3 + 8 x 9 + 10 x 16 = 259

  Do đó, ma trận ab = ⎡⎣⎢136215163380424371172386259⎤⎦⎥

  Tính chất của phép nhân ma trận

  Sau đây là các thuộc tính của phép nhân ma trận:

  Trao đổi thuộc tính

  Phép nhân ma trận không có tính chất giao hoán.

  Giả sử, nếu a và b là hai ma trận 2×2,

  Nào

  Trong phép nhân ma trận, thứ tự quan trọng.

  Ví dụ,

  Nếu a = [1324] và b = [3124] là hai ma trận thì

  a × b = [1324] × [3124]

  a × b = [5131022]

  Tuy nhiên,

  b × a = [3124] × [1324]

  b × a = [9131418]

  Đây là ma trận ab ba.

  Vậy phép nhân hai ma trận không có tính chất giao hoán.

  Bất động sản thống nhất

  Nếu a, b, c là ba ma trận thì tính kết hợp của phép nhân ma trận nói như vậy

  (ab) c = a (bc)

  Cho a = [1121]

  b = [3122]

  c=[0213]

  lhs = (ab)c

  a × b = [1121] × [3122]

  a × b = [5464]

  ( a b ) c= [5464] × [0213]

  ( a b ) c= [số 12 82316]

  rhs = a (bc)

  bc=[3122]×[0213]

  b c= [4497]

  a ( b c ) = [1121] × [4497]

  a ( b c ) = [số 12 82316]

  Điều này chứng tỏ tính kết hợp của phép nhân ma trận.

  Tính chất phân tán

  Nếu a, b và c là ba ma trận thì theo luật phân phối của phép nhân ma trận

  • (b + c) a = ba + ca
  • a (b + c) = ab + ac

  Thuộc tính nhận dạng đa lõi

  Biểu diễn đẳng thức của phép nhân ma trận,

  1. Tôi = Tôi. một = một

  trong đó a là ma trận cấp n × n và ‘i’ là ma trận đơn vị bậc n.

  Cho a = [2136] và i = [1001]

  A. tôi = [2136] × [1001]

  A. tôi=[2136]=a

  Thuộc tính thứ nguyên

  Trong phép nhân ma trận, tích của ma trận m × n và n × a là ma trận m × a.

  Ví dụ, ma trận a là ma trận 2×3, ma trận b là ma trận 3×4 thì ab là ma trận 2×4.

  Tính chất cấp số nhân của số 0

  Nếu một ma trận được nhân với một ma trận bằng không, thì ma trận kết quả là một ma trận bằng không.

  Nếu a = [2112] nhân với ma trận 0 (nghĩa là) [0000], tích sẽ trở thành [0000]

  Ví dụ đã giải quyết

  Phần sau giải thích phép nhân ma trận 4 × 4 theo hai ma trận 4 × 4 a và b.

  a = ⎡⎣⎢⎢⎢74141314#82171512666394⎤⎦⎥⎥⎥, b = ⎡⎣⎢⎢⎢5#813671663144#822944⎤⎦⎥⎥⎥

  Làm theo các bước tương tự như hai ví dụ trước, chúng ta có thể xây dựng một ma trận ab.

  ab = 378258370223381237497251286190346266224140277129⎤⎦⎥⎥⎥

  Bài tập nhân ma trận

  Khắc phục các vấn đề sau:

  1. Sản phẩm được tìm thấy: 3 [7251]
  2. Rút gọn ma trận 3 × 3 sau: ⎡⎣⎢121631215⎤⎦⎥×⎡⎣⎢142số 826731⎤⎦⎥
  3. Nếu a = [5931] và b = [16012], hãy tìm tích của ab
  4. Tìm tích của ma trận, nếu a=⎡⎣⎢421⎤⎦⎥ và [246]
  5. Phép tính: – 47㎡⎣⎢- 224935⎤⎦⎥

  Tìm hiểu thêm về ma trận và các chủ đề liên quan khác theo cách vui vẻ và thú vị. Tải xuống byju’s – Ứng dụng học tập ngay bây giờ.

  Câu hỏi thường gặp

  Phép nhân ma trận là gì?

  Phép nhân ma trận là phương pháp nhân hai ma trận để thu được kết quả là một ma trận. Đây là một hoạt động nhị phân.

  Làm thế nào để nhân hai ma trận đã cho?

  Để nhân một ma trận với một ma trận khác, trước hết ta cần kiểm tra xem số cột của ma trận thứ nhất có bằng số hàng của ma trận thứ hai hay không. Bây giờ nhân mỗi phần tử của cột của ma trận thứ nhất với mỗi phần tử của hàng của ma trận thứ hai và cộng tất cả chúng. Chúng ta cần thực hiện tích vô hướng của các cột và hàng ở đây.

  Kết quả của phép nhân ma trận (2×3) và (3×3) là gì?

  Kết quả của phép nhân ma trận (2×3) và (3×3) sẽ chỉ là ma trận 2×3.

  Làm thế nào để nhân ma trận 3 × 3 3?

  Nhân mỗi hàng của ma trận thứ nhất với mỗi cột của ma trận thứ hai và cộng tất cả để được phần tử đầu tiên. Tương tự, nhân và cộng các phần tử của hai ma trận cột và hàng để được các phần tử của tích hai ma trận 3×3.

  Làm thế nào để tìm tích của hai ma trận?

  Nếu a là ma trận am×n, b là ma trận ap×q, thì phép nhân của a và b được biểu diễn dưới dạng một mạng, chẳng hạn như: c = ab Vậy, c sẽ là ma trận m×q.

  Hệ công thức ma trận cho phương trình tuyến tính

  Nhân hai ma trận

  Báo cáo sự cố

  Trong bài toán “nhân hai ma trận”, chúng ta được cho hai ma trận. Chúng ta phải nhân các ma trận này và in ra kết quả hoặc kết quả cuối cùng của ma trận. Ở đây, điều kiện cần và đủ là số cột của ma trận a phải bằng số hàng của ma trận b. Nếu điều kiện này không đúng, thì chúng ta không thể nhân các ma trận này với nhau.

  Định dạng đầu vào

  Hàng đầu tiên

  chứa bốn giá trị nguyên r1, c1, r2, c2. trong đó r1 và c1 đại diện cho số hàng và số cột của ma trận đầu tiên. Trong đó r2 và c2 là số hàng và số cột của ma trận thứ hai.

  r1 Hàng tiếp theo chứa giá trị số nguyên c1.

  Các dòng

  và r2 sau đây chứa giá trị nguyên c2.

  Định dạng đầu ra

  In ma trận cuối cùng sau phép nhân, với mỗi dòng bắt đầu từ một dòng mới và mỗi khoảng trắng trong mỗi dòng phân tách các phần tử.

  Ràng buộc

  • 1 <= r1, c1, r2, c2 <= 2000.
  • 1 <= |m[i][j] | <= 10^9 trong đó m là vị trí của ma trận và phần tử tại hàng i, cột j.

  Ví dụ

  Giải thích: Trong ví dụ trên, chúng ta lấy phần tử đầu tiên trong kết quả bằng cách nhân tất cả các phần tử tương ứng trong hàng đầu tiên của ma trận a với các phần tử trong cột đầu tiên của ma trận b và cộng các phần tử Tương tự, để xuất phần tử thứ hai của hàng đầu tiên, ta cần lấy hàng đầu tiên của ma trận a và cột thứ hai của ma trận b. Bằng cách này, chúng tôi nhận được tất cả các phần tử trong ma trận đầu ra.

  Đây là một ví dụ ngẫu nhiên về phép nhân ma trận.

  Thuật toán nhân hai ma trận

  1. Chỉ cần chạy ba vòng. 2. Lặp qua từng hàng trong ma trận a sử dụng biến i.3. Trong vòng lặp trên, mỗi cột trong ma trận b được lặp lại bằng cách sử dụng biến j.4. Trong hai vòng lặp trên, mỗi phần tử hàng và biến k của ma trận a và biến k của mỗi phần tử cột của ma trận b được lặp lần lượt là a[i][k] và b[k][j].5. Chúng ta sẽ tìm tích của từng phần tử hàng trong a với từng phần tử cột trong b. Nghĩa là, a[i][k]*b[k][j] và tất cả các tích được tính tổng và lưu trữ trong một ma trận c mới, đó là c[i][j].6. Ma trận c là đầu ra của phép nhân.

  Triển khai

  Chương trình C++ để nhân hai ma trận

  Mã

  Hướng dẫn nhân hai ma trận bằng máy tính casio fx570es plus

  Tính ma trận a nhân b

  ✅Cách học ⭐️⭐️⭐️⭐️⭐️

  🎓Gia sư toán cao cấp

  Đang xem: 20 lời chúc Kỷ Niệm Ngày Cưới dành cho Vợ, cho Chồng Hay Nhất