Untitled12
LU and PLU Decompositions¶
Gaussian elimination can be interpreted as:
Copyright By PowCoder代写 加微信 powcoder
A = L U = \begin{bmatrix} \times \\ \vdots & \ddots \\ \times & \cdots & \times
\end{bmatrix} \begin{bmatrix} \times & \cdots & \times \\ & \ddots & \vdots \\ && \times
\end{bmatrix}
Gaussian elimination with pivoting can be interpreted as:
A = P^\top L U = P_\sigma^\top\begin{bmatrix} \times \\ \vdots & \ddots \\ \times & \cdots & \times
\end{bmatrix} \begin{bmatrix} \times & \cdots & \times \\ & \ddots & \vdots \\ && \times
\end{bmatrix}
using LinearAlgebra, BenchmarkTools
A = randn(n,n)
@btime qr(A);
203.301 μs (7 allocations: 134.55 KiB)
@btime lu(A); # returns the PLU Decomposition
55.969 μs (4 allocations: 79.08 KiB)
b = rand(n);
norm(lu(A) \ b – A \ b)
norm(qr(A) \ b – A \ b)
8.597325713189271e-14
norm(lu(A) \ b – big.(A) \ b)
1.425358539790752198650802673203131638232571083112364022139213085517791007107324e-13
norm(qr(A) \ b – big.(A) \ b)
7.927522338547764273693946389183225501504147654085037810246615786067216082179432e-14
Conclusion:
PLU decompositions are 4x faster, and only slightly less accurate than QR (on this example)
WARNING there is an extremely small chance PLU will give very inaccurate results, whereas QR is fine.
LU Decomposition¶
L_{n-1} \cdots L_1 A = U
L = L_1^{-1}\cdots L_{n-1}^{-1}
L,U = lu(A, NoPivot())
norm(L*U – A)
6.2001239763046875e-12
A = [2 1 1;
n = size(A,1)
L₁ = Matrix(1.0I, n, n)
L₁[2:end,1] = -A[2:end,1]/A[1,1]
L₂ = Matrix(1.0I, n, n)
L₂[3:end,2] = -A₁[3:end,2]/A₁[2,2]
3×3 Matrix{Float64}:
2.0 1.0 1.0
0.0 3.0 8.0
0.0 0.0 0.166667
function lu_nopivot(A)
n = size(A,1)
syntax: incomplete: “function” at In[40]:1 requires end
Stacktrace:
[1] top-level scope
@ In[40]:1
@ ./boot.jl:373 [inlined]
[3] include_string(mapexpr::typeof(REPL.softscope), mod::Module, code::String, filename::String)
@ Base ./loading.jl:1196
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com