Fixed-point computation and seismic waveform tomography

This dissertation is comprised of two parts: fixed-point computation and seismic waveform tomography. In the first part, I consider the problem of approximating fixed points of multivariate contractive and nonexpanding functions whose Lipschitz constant is close or equal to 1. Both absolute and residual error criteria are utilized as termination conditions. The circumscribed ellipsoid (CE) algorithm is shown to be able to approximate fixed points in a larger class of functions than possible in previous research. A function in this class is globally expanding but contractive or nonexpanding in the direction of fixed points. Line-search (LS) and circle-search (CS) methods are also developed for solving the fixed-point problem. The computational costs of both methods are lower than those of the CE method when the number of constraints is small. The LS method is well suited for almost linear functions while the CS method is well suited for rotational functions. To combine the strength of both methods, I developed an LS-CS hybrid method that in general is more efficient than either one of these methods. Various multivariate contractive and nonexpanding functions were implemented to test the performance of the proposed methods. The simple iteration (SI) and Newton-Raphson (NR) methods were compared with the CE, LS, CS, and LS-CS hybrid methods. The CE algorithm is an excellent method for low-dimensional functions with discontinuities and/or low regularity. However, the LS method is faster than the CE method in many cases because there is no need to construct an ellipsoid which requires solving an eigenvalue problem. However, the number of constraints for the LS, CS, LS-CS hybrid methods grows with the number of iterations.;In the second part, I develop an efficient multiscale method for time-domain waveform tomography. I propose filters that are more efficient than the previously used Hamming-windowed filter. A strategy for choosing optimal frequency bands is proposed to achieve high computational efficiency in the time domain. A staggered-grid, explicit finite-difference method with 4th -order accuracy in space and 2nd-order accuracy in time is used for forward modeling and the adjoint calculation. The adjoint method is utilized in the inversion for an efficient computation of the gradient directions. In the multiscale approach, multifrequency data and multiple grid sizes are used to partially overcome the severe local minima problem of waveform tomography. My method is successfully applied to both 1D and 2D heterogeneous models, and can accurately recover both the low and high wavenumber components of the velocity models. The inversion result for the 2D model also shows that the multiscale method is computationally efficient and converges faster compared to a conventional, single-scale method.