有效的数值算法课件.ppt

几种有效的数值算法 ;Fast Algorithm;1. 快速多极子方法;静电场和引力场 位势的多极子展开 矩阵向量乘积形式 ;FMM的应用综述1;多极子展开;2. Monte Carlo方法;收敛性 误差 对于独立同分布随机序列，由中心极限定理可知;3. 单纯形方法;4. Krylov子空间迭代法;5. QR算法;6. 快速排序方法;7. 快速Fourier变换;连续小波变换 为小波母函数 二进制离散小波 母函数通过伸缩平移变换生成一组正交的离散小波基函数， L2(R)中的函数 f(t) 可通过级数展开获得时域或频域的多尺度信息 离散小波变换 常用的小波正交基 Harr小波，Battle-Lemarie小波 等 WT用于信号分析，图像处理，地震勘探数据处理 等;9. 遗传算法;GA的基本算子: 选择、杂交、变异 Pseudo-code of GA 1. Choose initial population 2. Evaluate the fitness of each individual in the population 3. Repeat Select best-ranking individuals to reproduce b. Breed new generation through crossover and mutation (genetic operations) and give birth to offspring c. Evaluate the individual fitnesses of the offspring d. Replace worst ranked part of population with offspring 4. Until termination ;10. 多重网格方法;Ax=b的预条件迭代: M(xk+1-xk)=b-Axk , ek=xk+1-xk , rk=b-Axk MG可作为一种迭代法，也可作为PCG等迭代法的预条件子 Algorithm: MG (Ak, bk, uk, k) %V-循环结构的多重网格方法 Step1. If k is the coarsest level, uk= Inv(Ak) bk, return Step2. uk = Sk (Ak, bk, uk ) % 前光滑化(pre-smoothing), % Sk为光滑(smoothing)算子 Step3. rk = bk - Ak uk % 计算余量 Step4. bk-1 = Rk rk % Rk为限制(restriction)算子 Step5. vk-1 = 0 Step6. MG (Ak-1, b k-1, vk-1, k-1) % 粗网格上的多重网格迭代求解 Step7. uk = uk + Pk vk-1 % 粗网格校正, Pk为延拓(prolongation)算子 Step8. uk = Sk (Ak, bk, uk ) % 后光滑化(post-smoothing)