Phân tích ma trận: QR decomposition

Bài 1: QR decomposition
Bài 2: Trị riêng và vector riêng
Bài 3: Bài toán tìm trị riêng
Bài 4: Thuật toán QR

Blog này đã có lần đề cập đến LU decomposition, và bài này viết về QR decomposition hi vọng sẽ nối tiếp được chuỗi bài về các phương pháp phân tích ma trận. Ngoài ra đây là bài đầu tiên trong loạt 4 bài về trị riêng và thuật toán QR tìm trị riêng. Lẽ dĩ nhiên để hiểu thuật toán QR thì trước tiên cần phải biết về phép phân tích QR (QR decomposition).

Bài viết sẽ giới thiệu về động lực và ý tưởng của QR decomposition trong phần 1, sau đó điểm qua các thuật toán tính QR decomposition hiện có. Phần cuối cùng sẽ trình bày chi tiết về thuật toán  Householder để tính QR decomposition. Ý tưởng của phương pháp  Householder khá quan trọng và sẽ được dùng lại trong loạt bài này. Một cài đặt bằng MATLAB của thuật toán này cũng được cung cấp giúp người đọc hiểu rõ hơn về thuật toán.

1. Phân tích QR

1.1. Định nghĩa

Phân tích QR là một trong những vấn đề được quan tâm nhất trong Numerical Linear Algebra khoảng nửa cuối thế kỉ trước. Động cơ (motivation – tiếng Việt dùng từ nào cho hay?) của QR decomposition là nhiều khi chúng ta quan tâm tới các không gian tạo bởi các cột đầu tiên a_1, a_2, ... của ma trận A, nghĩa là các không gian \langle a_1\rangle, \langle a_1, a_2\rangle, \langle a_1, a_2, a_3\rangle, \ldots. Ta có:

\langle a_1\rangle \subseteq \langle a_1, a_2\rangle \subseteq \langle a_1, a_2, a_3\rangle\subseteq\ldots

trong đó \langle a_1\rangle là không gian một chiều tạo bởi cơ sở \{a_1\}, \langle a_1, a_2\rangle là không gian 2 chiều tạo bởi \{a_1, a_2\}, v.v…. (tất nhiên các a_i phải độc lập tuyến tính).

Mặc dù các không gian này tồn tại và ta biết tập sinh của chúng, nhưng không chắc rằng các vector cơ sở này trực giao với nhau. Ý tưởng chính của phân tích QR là đi tìm một dãy các vector q_1, q_2, q_3, \ldots độc lập tuyến tính, trực giao và tạo thành cơ sở trực chuẩn (orthonomal basis) cho các không gian nói trên.

Nói một cách chính xác, cho trước ma trận A\in \mathbb{C}^{m\times n}, m\geq nhạng là n (nghĩa là các cột của A độc lập tuyến tính). Ta muốn tìm dãy các vector q_1, q_2, q_3, \ldots thỏa tính chất:

\langle q_1, q_2, \ldots, q_j\rangle = \langle a_1, a_2, \ldots, a_j\rangle, \forall j = 1,\ldots,n    (1)

Để đảm bảo tính chất này, với mỗi j thì a_1, a_2, \ldots, a_j là tổ hợp tuyến tính của q_1, q_2, \ldots, q_j. Nói cách khác điều kiện (1) có thể viết lại như sau

\displaystyle \Biggl[\begin{array}{c|c|c|c}a_1&a_2&\ldots&a_n\end{array}\Biggr]=\Biggl[\begin{array}{c|c|c|c}q_1&q_2&\ldots&q_n\end{array}\Biggr]\left[\begin{array}{cccc}r_{11}&r_{12}&\ldots&r_1n\\\;&r_{22}&\ldots&\ldots\\\;&\;&\cdots&\ldots\\\;&\;&\;&r_{nn}\\\end{array}\right]

hay ngắn gọn hơn:

\displaystyle A = \hat{Q}\hat{R}        (2)

trong đó \hat{Q}\in\mathbb{C}^{m\times n} có các cột là các vector trực giao, và \hat{R}\in\mathbb{C}^{n\times n} là ma trận tam giác trên. Phép phân tích như vậy (nếu có) gọi là phân tích QR rút gọn của ma trận A.

Với ma trận A như trên, dạng phân tích QR đầy đủ của A chính là sự mở rộng của QR rút gọn bằng cách thêm vào bên phải của \hat{Q} m-n vector trực chuẩn để tạo thành ma trận unitary Q có m hàng và m cột. Ma trận \hat{R} cũng được thêm vào bên dưới m-n dòng zero tạo thành ma trận tam giác trên R với m dòng và n cột.

A = \hat{Q}\hat{R} = \Biggl[\begin{array}{c|c}\hat{Q}&Q_1\end{array}\Biggr]\Biggl[\begin{array}{c}\hat{R}\\\mathbf{0} \end{array}\Biggr]=QR       (3)

Lưu ý rằng trong dạng phân tích QR đầy đủ, m-n cột bên phải của Q (các q_j với j > n) là các vector trực giao với không gian range(A). Nói cách khác nếu n cột của A độc lập tuyến tính, thì m-n cột bên phải của Q tạo thành cơ sở cho không gian trực giao của range(A), hay cũng là không gian null(A*).

Ví dụ: Xét ma trận A = \left[\begin{array}{cc}1&2\\2&1\end{array}\right]. Khi đó dùng MATLAB ta tính được

A = QR = \left[\begin{array}{cc}0.4472&0.8944\\ 0.8944&-0.4472\end{array}\right]\left[\begin{array}{cc}2.2361&1.7889\\ 0&1.3416\end{array}\right]

Ta nhận thấy mặc dù các cột của A là độc lập tuyến tính nhưng không vuông góc (trực giao), trong khi các cột của Q là 2 vector vuông góc, và R là ma trận tam giác trên.

1.2. Sự tồn tại và tính duy nhất

Mọi ma trận A\in\mathbb{C}^{m\times n} (m\geq n) đều có phân tích QR đầy đủ, do đó có phân tích QR rút gọn.

Mọi ma trận A\in\mathbb{C}^{m\times n} (m\geq n) hạng đủ có duy nhất phân tích QR rút gọn A=\hat{Q}\hat{R} với r_{jj} > 0.

Giả sử A = \hat{Q}\hat{R} là một phân tích QR rút gọn. Khi đó nếu ta nhân cột thứ i của \hat{Q} với giá trị vô hướng z và dòng thứ i của \hat{R} với z^{-1}|z|=1 thì ta được một khai triển QR rút gọn mới của A.

2. Các thuật toán tính QR decomposition

Có 3 phương pháp thường được dùng để tính phân tích QR của ma trận là Trực chuẩn hóa Gram-Schmidt (Gram-Schmidt orthogonalization), Chéo hóa Householder (Householder triangularization) và phép quay Givens. Phần này sẽ nêu sơ qua tư tưởng chính của các phương pháp và chi phí tính toán của chúng. Phần 3 trình bày chi tiết về phương pháp Householder.

Trong phương pháp Gram-Schmidt, ta lần lượt nhân bên phải ma trận A với các ma trận tam giác trên R_1, R_2, \dotsc R_n sao cho ma trận kết quả cuối cùng

A\underset{\hat{R}^{-1}}{\underbrace{R_1R_2\ldots R_n}}=\hat{Q}

có các cột là các vector trực giao. Ma trận tích \hat{R}=R_n^{-1}\ldots R_2^{-1}R_1^{-1} cũng là ma trận tam giác trên. Do đó A=\hat{Q}\hat{R} là phân tích QR rút gọn của A. Tất nhiên việc chọn các ma trận R_i cần một chút tinh tế. Ở đây chúng ta không quan tâm đến thuật toán này.

Ngược lại, phương pháp Householder lần lượt nhân bên trái ma trận A với các ma trận unitary cơ sở Q_1, Q_2, \ldots Q_n sao cho ma trận kết quả

\underset{Q^{*}}{\underbrace{Q_n\ldots Q_2Q_1}}A=R

là ma trận tam giác trên. Tích Q=Q_1^*Q_2^*\ldots Q_n^* cũng là unitary, do đó A=QR là phân tích QR đầy đủ của A (Để ý rằng do Q_i là ma trận unitary nên Q_i^*=Q_i^{-1}). Bảng sau tóm tắt một số tính chất của hai phương pháp này.

Phương pháp Đặc điểm Độ phức tạp Stable
Gram-Schmidt Triangular orthogonalization
Trực giao hóa ma trận A bằng các ma trận tam giác
2mn^2 No
Householder Orthogonal triangularization
Tam giác hóa ma trận A bằng các ma trận trực giao
2mn^2 - \frac{2}{3}n^3 Yes

Nhìn chung phương pháp Householder tỏ ra stable hơn Gram-Schmidt. Với ma trận A\in\mathbb{C}^{m\times n} thì phương pháp Gram-Schmidt có độ phức tạp tính toán khoảng 2mn^2, trong khi Householder có độ phức tạp tính toán khoảng 2mn^2 - \frac{2}{3}n^3. Phần tiếp theo sẽ trình bày chi tiết thuật toán Householder.

3. Thuật toán Householder

3.1. Tư tưởng

Phương pháp lặp Householder để tính QR decomposition được Alston Householder đề xuất năm 1958. Ý tưởng chính của phương pháp này là chọn các ma trận unitary Q_k  sao cho Q_n\ldots Q_2Q_1A là ma trận tam giác trên.

Để làm được điều đó, Q_k phải được chọn sao cho nó sẽ làm cho các phần tử bên dưới đường chéo chính của cột k trong ma trận A thành 0. Ví dụ với ma trận 5\times 3 thì sẽ cần 3 phép nhân ma trận như sau (trong đó \times là các phần tử không nhất thiết bằng 0, và các phần tử in đậm là những phần tử thay đổi sau mỗi bước).

\underset{A}{\left[\begin{array}{ccc}\times & \times & \times\\\times & \times & \times\\\times & \times & \times\\\times & \times & \times\\\times & \times & \times\end{array}\right]}\underrightarrow{Q_{1}}\underset{Q_{1}A}{\left[\begin{array}{ccc}\boldsymbol{\times} & \boldsymbol{\times} & \boldsymbol{\times}\\\mathbf{0} & \boldsymbol{\times} & \boldsymbol{\times}\\\mathbf{0} & \boldsymbol{\times} & \boldsymbol{\times}\\\mathbf{0} & \boldsymbol{\times} & \boldsymbol{\times}\\\mathbf{0} & \boldsymbol{\times} & \boldsymbol{\times}\end{array}\right]}\underrightarrow{Q_{2}}\underset{Q_{2}Q_{1}A}{\left[\begin{array}{ccc}\times & \times & \times\\ \; & \boldsymbol{\times} & \boldsymbol{\times}\\ & \mathbf{0} & \boldsymbol{\times}\\ \; & \mathbf{0} & \boldsymbol{\times}\\ \; & \mathbf{0} & \boldsymbol{\times}\end{array}\right]}\underrightarrow{Q_{3}}\underset{Q_{3}Q_{2}Q_{1}A}{\left[\begin{array}{ccc}\times & \times & \times\\ \; & \times & \times\\ \; & \; & \boldsymbol{\times}\\ \; & \; & \mathbf{0}\\\; & \; & \mathbf{0}\end{array}\right]}

Một cách tổng quát, Q_k sẽ làm việc trên các dòng từ k đến m của A. Tại thời điểm bắt đầu của bước thứ k, trên các dòng từ k đến m đã có sẵn k-1 cột bằng 0. Việc áp Q_k lên những cột này cũng có nghĩa là thực hiện tổ hợp tuyến tính của chúng, và tổ hợp tuyến tính của những dòng bằng 0 cũng bằng 0. Cuối cùng sau n bước, tất cả các phần tử bên dưới đường chéo chính đều bằng 0, và Q_n\ldots Q_2Q_1A=R là ma trận tam giác trên.

Nhưng vấn đề là làm thế nào để chọn ma trận Q_k phù hợp? Cách tiếp cận chuẩn mực thường sử dụng Q_k là ma trận unitary có dạng sau:

Q_k=\left[\begin{array}{cc}I& 0\\ 0&F\end{array}\right]        (1)

trong đó I là ma trận indentity kích thước (k-1)\times (k-1)F là ma trận unitary kích thước (m-k+1)\times (m-k+1). Khi thực hiện phép nhân Q_k với A thì F có nhiệm vụ tạo các giá trị 0 trên cột thứ k của A. Phương pháp Householder sử dụng một dạng ma trận F đặc biệt gọi là Householder reflector.

Giả sử tại bước thứ k, ta gọi các phần tử từ k đến m của cột k là vector x \in\mathbb{C}^{m-k+1}. Để có thể gán 0 cho các phần tử bên dưới đường chéo chính thì F phải thực hiện được ánh xạ sau

x=\left[\begin{array}{c}  \times\\  \times\\  \times\\  \vdots\\  \times\end{array}\right]\qquad\underrightarrow{\quad F\quad}\qquad Fx=\left[\begin{array}{c}  \parallel x\parallel\\  0\\  0\\  \vdots\\  0\end{array}\right]=\parallel x\parallel e_{1}   (2)

Householder reflection

Hình 1: Householder reflection

Hình 1 thể hiện ý tưởng để thực hiện ánh xạ này. Ma trận F thể hiện phép đối xứng điểm x qua siêu phẳng H vuông góc với v = \parallel x\parallel e_1 - x. Khi đó đối xứng của x qua H sẽ là \parallel x \parallel e_1. Ta biết phép chiếu trực giao một điểm y\in \mathbb{C}^m lên siêu phẳng H được biểu diễn bằng ma trận

Py = \left(I-\frac{vv^*}{v^*v}\right)y=y-v\left(\frac{v^*y}{v^*v}\right)       (3)

Như vậy để tìm điểm đối xứng của y qua H, ta cần tiến thêm một đoạn gấp đôi trên cùng phương đó. Do vậy Householder reflector Fy sẽ là

Fy=\left(I-2\frac{vv^*}{v^*v}\right)y=y-2v\left(\frac{v^*y}{v^*v}\right)       (4)

Do đó ma trận F là

F=I-2\frac{vv^*}{v^*v}      (5)

Dễ dàng ta thấy F^*=F\left(I-2\frac{vv^*}{v^*v}\right)\left(I-2\frac{vv^*}{v^*v}\right)=I nên F^{-1}=F=F^*, suy ra F là ma trận unitary.

Hình 1 đã được vẽ đơn giản hóa cho dễ hiểu. Trên thực tế có thể có nhiều siêu phẳng H khác nhau để đối xứng điểm x thành z\parallel x\parallel e_1 với z là giá trị vô hướng nào đó sao cho |z| = 1. Trong trường hợp 2 chiều đang xét, nếu A là ma trận phức thì có thể có một circle các điểm đối xứng, trong trường hợp là số thực thì cũng có đến 2 phép đối xứng qua 2 siêu phẳng H^+H^- khác nhau, như được vẽ trong Hình 2.

Householder reflection

Hình 2: Householder reflection. Có 2 khả năng có thể chọn. Để tránh lỗi làm tròn trong quá trình tính toán, cần chọn phép đối xứng sao cho ||v|| lớn nhất có thể.

Về mặt toán học, ta có thể chọn bất kì phép đối xứng nào vì chúng đều thỏa mãn yêu cầu. Tuy nhiên đến đây thì vai trò của việc tính toán sẽ ảnh hưởng đến việc chọn phép đối xứng nào là “tốt nhất”. Chúng ta muốn chọn phép đối xứng sao cho z\parallel x\parallel e_1 không quá gần với bản thân x, để phép trừ v =z\parallel x\parallel e_1 - x không bị làm tròn về 0 (nếu v = 0 thì theo (5), ma trận F sẽ không tính được). Để làm được điều này, ta có thể chọn z=-sign(x_1), trong đó x_1 là phần tử đầu tiên của x. Như vậy vector pháp tuyến của siêu phẳng H sẽ là v = -sign(x_1)\parallel x\parallel e_1 - x, hay bỏ các dấu trừ, ta có

v = sign(x_1)\parallel x\parallel e_1 + x    (6)

Tất nhiên ta giả sử nếu x_1 = 0 thì sign(x_1) = 1.

Tại sao cách chọn này lại tốt? Nhìn vào Hình 2, nếu góc giữa H^+ và trục e_1 quá nhỏ thì vector v = \parallel x\parallel e_1 - x trở nên rất nhỏ so với x\parallel x\parallel e_1. Do đó v có thể bằng 0 do việc làm tròn số khi tính toán. Bằng cách chọn v như (6), ta có thể tránh hiện tượng này do ta có thể đảm bảo chắc chắn rằng \parallel v\parallel không thể nhỏ hơn \parallel x\parallel.

3.2. Thuật  toán

Tới đây đã có thể phát biểu đầy đủ thuật toán Householder để tìm QR factorization của ma trận. Để ngắn gọn, ta sẽ sử dụng kí hiệu A(i:i',j:j') để chỉ ma trận con kích thước (i'-i+1)\times (j'-j+1) của A, có phần tử a_{ij} là góc trên trái và a_{i'j'} là góc dưới phải. Nếu ma trận con đó là vector cột hoặc dòng thì kí hiệu tương ứng là A(i:i',j)A(i,j:j').

Thuật toán Householder sau đây sẽ tìm QR decomposition của ma trận A kích thước m\times n, m\geq n. Ma trận kết quả R được lưu trong A sau khi kết thúc thuật toán. Ngoài ra các vector v_k cũng được tính để sử dụng trong các bước sau.

Thuật toán 1: Tính QR decomposition bằng Householder

for k=1 to n do

x = A(k:m, k)

v_k = sign(x_1)\parallel x\parallel_2e_1 + x

v_k = \frac{v_k}{\parallel v_k\parallel_2}

A(k:m,k:n)=A(k:m,k:n)-2v_k\left(v_k^*A(k:m,k:n)\right)

Thuật toán này chỉ tính ma trận tam giác R. Để tính Q ta cần thêm một vòng lặp nữa. Tuy nhiên trong một số ứng dụng, ta không cần tính Q một cách tường minh, mà có thể sử dụng công thức sau:

Q^* = Q_n\ldots Q_2Q_1    (7)

Hay ma trận chuyển vị liên hợp của nó (nhớ rằng các Q_i là Hermitian nên Q_i^*=Q_i):

Q = Q_1Q_2\ldots Q_n     (8)

Bằng cách tận dụng các vector v_k, ta có thể tính trực tiếp các tích Q^*x hoặc Qx với vector x\in \mathbb{C}^m bằng 2 thuật toán sau:

Thuật toán 2: Tính tích Q^*x

for k = 1 to n do

x(k:m) = x(k:m) - 2v_k\left(v_k^*x(k:m)\right)

Thuật toán 3: Tính tích Qx

for k = n downto 1 do

x(k:m) = x(k:m) - 2v_k\left(v_k^*x(k:m)\right)

Đương nhiên đôi khi ta cũng muốn tạo lại ma trận Q đầy đủ, khi đó cách dễ nhất là tính tích QI bằng cách sử dụng thuật toán 3 để tính Qe_1, Qe_2, \dotsc Qe_m. Nếu chỉ cần tính \hat{Q} thay cho Q thì chỉ cần tính đến Qe_n.

3.3. Cài đặt MATLAB

Cách tốt nhất để hiểu một thuật toán là cài đặt và chạy nó. Phần này cung cấp cài đặt thuật toán QR bằng MATLAB. Tất nhiên MATLAB cũng đã cung cấp thuật toán này bằng hàm qr() nhưng việc cài đặt lại sẽ giúp ta hiểu rõ hơn thuật toán này.


function [ R, Q ] = myqr( A )
  %MYQR Summary of this function goes here
  %   Detailed explanation goes here
  R = A;
  [m, n] = size(R);
  V = zeros(m, n);

  assert(m >= n, 'm should be geq to n');

  for k=1:n
    x = R(k:m,k);
    e = zeros(m-k+1, 1);
    e(1) = 1;
    v = sign(x(1))*norm(x, 2)*e + x;
    v = v./norm(v, 2);
    R(k:m,k:n)=R(k:m,k:n) - 2*v*(v'*R(k:m,k:n));

    V(k:m, k) = v;
  end

  if (nargout == 2)
    Q = zeros(m, m);
    for i=1:m
      ei = zeros(m, 1);
      ei(i) = 1;
      for k=n:-1:1
        ei = ei - 2*V(:,k)*(V(:,k)'*ei);
      end
      Q(:,i) = ei;
    end
  end
end

Tất nhiên hàm này chỉ thực hiện thuật toán, không có những kiểm tra chi tiết về tính hợp lệ của ma trận A. Khi chạy hàm này ta thấy kết quả sai khác với hàm qr() của MATLAB về dấu của các trị riêng phần tử trên đường chéo của R, có lẽ do MATLAB cố ý chọn lời giải sao cho các phần tử trên đường chéo của R đều là số dương (theo đúng tinh thần của phân tích QR được phát biểu trong phần 1.2).


>> a = [1 2; 2 1];

>> [q1, r1] = qr(a);

>> [r2, q2] = myqr(a);

>> q1
  q1 =
    0.4472    0.8944
    0.8944   -0.4472
>> q2
  q2 =
    -0.4472    0.8944
    -0.8944   -0.4472
>> r1
  r1 =
    2.2361    1.7889
    0    1.3416
>> r2
  r2 =
    -2.2361   -1.7889
    0    1.3416

Bài tiếp theo sẽ trình bày về thuật toán QR để tìm trị riêng của ma trận.

Advertisements

16 comments

  1. Chào anh, ở thuật toán 1, nếu vector x là vector 0 thì sẽ không chuẩn hóa được vector vk, nên bước sau không thực hiện được, trường hợp đó thì mình sẽ giải quyết thế nào vậy anh?
    Em còn một thắc mắc nữa, khi em cài đặt thử thuật toán QR decomposition, thì sau quá trình lặp em tìm được gần đúng giá trị ma trận Q, R, nhưng lúc này khi lấy QR thì kết quả có một số phần tử sai số khá nhiều so với ma trận A ( sai số 2 – 5 đơn vị trong một số lần em test thử), như vậy có làm ảnh hưởng nhiều đối với kết quả cuối cùng là trị riêng không ạ?
    Cám ơn anh ạ!

    1. Hi Thịnh,
      Mục tiêu của thuật toán 1 là biến ma trận A thành ma trận R là tam giác trên, nên nếu tại bước k, vector x = 0 thì cột thứ k của A nghiễm nhiên đã có các phần tử bằng 0 bên dưới đường chéo chính, ko cần xử lí gì thêm.
      Sai số 2-5 đơn vị là quá lớn, e nên kiểm tra lại thuật toán, các chi tiết như: có hỗ trợ ma trận không vuông (m khác n) hay ko, cách lấy chỉ số của phần tử v.v… Nếu cần thì có thể post mã nguồn và các ma trận “có vấn đề” lên đây, anh sẽ xem thử.

  2. Chào anh em đang muốn tìm hiểu pp householder để giải hệ phương trình tt để phục vụ cho đồ án tốt nghiệp
    Vậy a có thể giải thích rõ hơn cho em đc không ạ
    Và a có thể cho em biết là cài đặt nó có khó không( không phải là trên matlab)

  3. Hi Mẫn,
    Anh nghĩ bài này viết rất rõ về Householder rồi, em có thể tìm thêm trên wiki và 1 số tài liệu khác.
    Em định cài thuật toán này làm gì? Đa phần các thuật toán Numerical Linear Algebra đều có nhiều trường hợp đặc biệt (ma trận suy biến, lỗi do làm tròn v.v…) nên để cài đặt thuật toán chủ yếu thì dễ, nhưng để cài đặt đó làm việc được với mọi ma trận thì khó, vì phải xét nhiều trường hợp riêng.
    Do đó theo anh em không nên cài lại làm gì. Các thuật toán này đã được cài sẵn trong BLAS (Intel MKL v.v…) và được tối ưu rồi. Em cài lại không tốt bằng người ta làm đâu 🙂

    1. Vâng thưa anh vậy nếu như ta dùng phương pháp lặp seidel để giải thì các khi cài đặt thì ta có cách nào để xét đến các trường hợp là phần tử ở đường chéo chính bằng không (không thể chuyển về dạng x = a + bx) hay là xét điều kiện hội tụ của phương pháp không ạ

  4. anh ơi cho em hỏi chuyển từ phép phân tích QR sang LQ thế nào ạ . em thấy trong matlab chỉ có phép phân tích qr. cảm ơn anh

  5. Hi anh Vũ !
    Không biết anh có thể viết thuật giải bằng mã giả hoặc lời văn từng bước được không ạ ?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s