ハウスホルダー法による行列三重対角化の可視化
ヤコビ法による行列対角化の可視化の時と同様に、ハウスホルダー法による三重対角化の様子を可視化する。
処理としては、ヤコビ法と似ていて、行列Aにハウスホルダー行列Pを繰り返し両側からかける。
PをAの両側からかけることで、元行列の特定の行・列ベクトルに鏡像変換をかけたことになる。
行列三重対角化以外に、QR分解のための手法としても用いられる。
cf. https://ja.wikipedia.org/wiki/ハウスホルダー変換
library("fields")
library("stringr")
HouseholderMatrix <- function(A, step){
x <- A[, step]
y <- rep(0, length(x))
y[1:step] <- A[1:step, step]
s <- sqrt(sum(A[setdiff(1:nrow(A), 1:step), step]^2))
y[step+1] <- - s
u <- (x - y) / norm(as.matrix(x - y), "F")
P <- diag(1, nrow(A))
P <- P - 2 * u %*% t(u)
P
}
plotA <- function(A, step){
image.plot(log10(A[, ncol(A):1]+1),
main=paste0("k = ", step),
xaxt="n", yaxt = "n")
if(step != nrow(A)-1){
pos <- seq(0, 1, length = nrow(A))
text(pos[step], 1-pos[(step+2):length(pos)], "×")
text(pos[(step+2):length(pos)], 1-pos[step], "×")
}
}
Householder <- function(A, viz=FALSE, viz.dir=""){
if(viz){
if(viz.dir==""){
plotA(A, 0)
Sys.sleep(0.2)
}else{
png(file=paste0(viz.dir, "/Step0000.png"))
plotA(A, 0)
dev.off()
}
}
U <- diag(1, nrow(A))
step <- 1
for(k in seq_len(nrow(A)-1)){
P <- HouseholderMatrix(A, step)
U <- U %*% P
A <- P %*% A %*% P # Update
if(viz){
if(viz.dir==""){
plotA(A, step)
Sys.sleep(0.2)
}else{
png(file=paste0(viz.dir, "/Step",
str_sub(paste0("000", step), start = -4),
".png"))
plotA(A, step)
dev.off()
}
}
step <- step + 1
}
list(U=U, Sigma=A)
}
# 30×30行列で実験
dir.create("HouseHolder", showWarnings=FALSE)
A <- matrix(runif(30*30), nrow=30, ncol=30)
A <- t(A) %*% A # 対称行列にする
out <- Householder(A, viz=TRUE, viz.dir="./Householder")
xは次のステップで0になる予定箇所。
行列Aが徐々に三重対角要素を残して疎な行列になっていく様子がわかる。
ヤコビ法の対角化と比べると、三重対角化は(行列Aの次数)-1分だけ処理をすればいいので、計算がすぐ終わることがわかる。
この三重対角行列にさらに二分法など別の手法を適用することにより、元の行列Aの固有値・固有ベクトルがもとめる。
密行列と比べて要素数も少ないので計算がかなり楽になる。
参考
Author And Source
この問題について(ハウスホルダー法による行列三重対角化の可視化), 我々は、より多くの情報をここで見つけました https://qiita.com/antiplastics/items/fc7b7b0066cbd823b6a6著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .